In this paper, we study the contextual multinomial logit (MNL) bandit problem in which a learning agent sequentially selects an assortment based on contextual information, and user feedback follows an MNL choice model. There has been a significant discrepancy between lower and upper regret bounds, particularly regarding the maximum assortment size $K$. Additionally, the variation in reward structures between these bounds complicates the quest for optimality. Under uniform rewards, where all items have the same expected reward, we establish a regret lower bound of $\Omega(d\sqrt{T/K})$ and propose a constant-time algorithm, OFU-MNL+, that achieves a matching upper bound of $\tilde{O}(d\sqrt{T/K})$. We also provide instance-dependent minimax regret bounds under uniform rewards. Under non-uniform rewards, we prove a lower bound of $\Omega(d\sqrt{T})$ and an upper bound of $\tilde{O}(d\sqrt{T})$, also achievable by OFU-MNL+. Our empirical studies support these theoretical findings. To the best of our knowledge, this is the first work in the contextual MNL bandit literature to prove minimax optimality -- for either uniform or non-uniform reward setting -- and to propose a computationally efficient algorithm that achieves this optimality up to logarithmic factors.
Paper
Similar papers
Peer review
Summary
This paper studied the minimax optimal regret for a series of contextual MNL bandit problems, covering rewards—uniform and non-uniform cases and varying the value of the outside option $v_0$. The authors first derive the regret lower bound that provides explicit dependence on the key parameters. Then they propose efficient algorithm OFU-MNL+ that achieves a matching upper bound up to a logarithm term. Simulations were conducted to demonstrate the tight dependence of the derived bounds.
Strengths
1. Despite many recent advances in contextual MNL bandit problems, however no previous studies have proven the minimax optimality. There has been a significant discrepancy between lower and upper regret bounds, particularly regarding the feature dimension $d$ and the maximum assortment size $K$. This paper closes this gap. The technical contribution is strong and sufficient. 2. In spite of a theoretical paper, it is well written and is easy to follow. I enjoy reading the paper.
Weaknesses
1. My major question is about Assumption 2, which requires the uniform lower bound for every item $i\in {\cal S}$ and any assortment set and all round $t$. Requiring $\kappa$ to be a constant would be a strong assumption in practice. Since $\min_i p_t(i|S,w) \le 1/K$, $\kappa$ would naturally depend on the size $K$. In this case, would it be possible to derive more tighter results by explicitly including $\kappa$ in the lower and upper bounds? Below are a few minor suggestions: 2. I would suggest to introduce Section 4 (Problem Setting) before Section 3 (Existing Gap). Readers who are not familiar with the contextual MNL bandit problems might be confusing while reading Section 3. 3. Section 3 overlaps with many discussions in the Introduction section. It might be helpful to shorten the discussion and add more discussions on (1) why proving the new lower and upper bound results is non-trivial; (2) providing some proof outlines on the key steps used in the proof. 4. In the Introduction, line 31 on page 1, it is helpful to add some clarification on the definition of $v_0$. The current terminology "utility of the outside option" is not very clear. 5. In line 162 on page 4, the authors mentioned that the set of items $[N]$ can vary over time. While I understand the assortment set $\cal S$ could change over time, I am confused how $[N]$ could vary over time. The notation $[N]$ means $\{1, \ldots, N\}$. What do you mean this set varies over time? Do you allow new items to enter the market or some items to be removed over time?
Questions
see Weakness
Rating
7
Confidence
4
Soundness
3
Presentation
4
Contribution
3
Limitations
N/A
Additional Comment by Authors
### **A. Proof of problem-dependent upper bound** We start the proof from line 748 in the proof of Theorem 2. \begin{align*} \sum\_{t=1}^T \nabla Q(\mathbf{u}\_t^\star)^\top (\mathbf{u}\_t - \mathbf{u}\_t^\star) \leq 2 \beta_T(\delta) \sum\_{t=1}^T \sum\_{i \in S_t} p_t(i \mid S_t, \mathbf{w}^\star)p_t(0 \mid S_t, \mathbf{w}^\star) \\| x\_{ti} \\|_{H_t^{-1}}. \end{align*} Let $g_t(S ; \mathbf{w}):= \sum\_{i \in S} p_t(i \mid S, \mathbf{w})p_t(0 \mid S, \mathbf{w}) \\| x\_{ti} \\|_{H_t^{-1}}$. Let $J_1 = \\{ t \in [T] \mid \sum\_{i \in S_t} p_t(i \mid S_t, \mathbf{w}^\star)p_t(0 \mid S_t, \mathbf{w}^\star) \geq \sum\_{i \in S_t} p_t(i \mid S_t, \mathbf{w}\_{t+1})p_t(0 \mid S_t, \mathbf{w}\_{t+1})\\\}$ and $J_2 = [T] \setminus J_1$. Thus, we get \begin{align*} \text{RHS} = 2 \beta_T(\delta) \sum\_{t=1}^T g_t(S_t; \mathbf{w}^\star) = 2 \beta_T(\delta) \sum\_{t \in J_1} g_t(S_t; \mathbf{w}^\star) + 2 \beta_T(\delta) \sum\_{t \in J_2} g_t(S_t; \mathbf{w}^\star). \end{align*} To bound $\sum_{t \in J_1} g_t(S_t; \mathbf{w}^\star)$, by the mean value theorem, we get \begin{align*} \sum\_{i \in J_1} g_t(S_t; \mathbf{w}^\star) = \sum\_{i \in J_1} g_t(S_t; \mathbf{w}\_{t+1}) + \sum\_{i \in J_1} \nabla\_{\mathbf{w}} g_t(S_t; \bar{\mathbf{w}}_t)^\top (\mathbf{w}^\star - \mathbf{w}\_{t+1}), \end{align*} where $\bar{\mathbf{w}}_t$ is the convex combination of $\mathbf{w}^\star$ and $\mathbf{w}\_{t+1}$. The first term can be bound by \begin{align*} \sum\_{t \in J_1} g_t(S_t; \mathbf{w}\_{t+1}) &\leq \sqrt{\sum\_{t\in J_1} \sum\_{i \in S_t} p_t(i \mid S_t, \mathbf{w}\_{t+1})p_t(0 \mid S_t, \mathbf{w}\_{t+1})} \sqrt{\sum\_{t \in J_1} \sum\_{i \in S_t} p_t(i \mid S_t, \mathbf{w}\_{t+1})p_t(0 \mid S_t, \mathbf{w}\_{t+1}) \\| x_{ti}\\|\_{H_t^{-1}}^2 } \\\\ &\leq \sqrt{\sum\_{t\in J_1} \sum\_{i \in S_t} p_t(i \mid S_t, \mathbf{w}^\star)p_t(0 \mid S_t, \mathbf{w}^\star)} \cdot \tilde{\mathcal{O}}( \sqrt{d} ) \leq \sqrt{\sum\_{t=1}^T \kappa_t^\star + \text{Reg}\_T} \cdot \tilde{\mathcal{O}}( \sqrt{d} ) , \end{align*} where the second-to-the last inequality holds by the definition of $J_1$ and the elliptical potential lemma in our paper, and the last inequality holds by Lemma 11 in Goyal and Perivier [24] with $\kappa_t^\star := \sum\_{i \in S_t^\star} p_t(i \mid S_t^\star, \mathbf{w}^\star)p_t(0 \mid S_t^\star, \mathbf{w}^\star)$. Moreover, the second term can be bounded by \begin{align*} \left|\sum\_{i \in J_1}\nabla_{\mathbf{w}} g_t(S_t; \bar{\mathbf{w}}\_t)\top (\mathbf{w}^\star - \mathbf{w}\_{t+1}) \right| &=\Bigg|\sum\_{t \in J_1} p_t(0 \mid S_t, \bar{\mathbf{w}}\_t) \sum_{i \in S_t}p_t(i \mid S_t, \bar{\mathbf{w}}\_t) x\_{ti}^\top (\mathbf{w}^\star - \mathbf{w}\_{t+1}) \\| x_{ti} \\|\_{H_t^{-1}} - 2 p_t(0 \mid S_t, \bar{\mathbf{w}}_t) \sum\_{i \in S_t}p_t(i \mid S_t, \bar{\mathbf{w}}\_t) \\| x\_{ti} \\|\_{H_t^{-1}} \sum\_{j \in S_t}p_t(j \mid S_t, \bar{\mathbf{w}}\_t) x\_{tj}^\top (\mathbf{w}^\star - \mathbf{w}\_{t+1}) \Bigg| \\\\ &\leq 3 \beta\_{T}(\delta) \sum\_{t=1}^T \max\_{i \in S_t} \\| x\_{ti} \\|\_{H_t^{-1}}^2 = \tilde{\mathcal{O}}(d^{3/2}/\kappa). \end{align*} Hence, we get $2 \beta_T(\delta) \sum_{t \in J_1} g_t(S_t; \mathbf{w}^\star) = \tilde{\mathcal{O}}\left( d \sqrt{\sum_{t=1}^T \kappa_t^\star + \text{Reg}_T} + d^{2}/\kappa \right)$. Now, we bound $\sum\_{t \in J_2} g_t(S_t; \mathbf{w}^\star)$. \begin{align*} \sum\_{t \in J_2} g_t(S_t; \mathbf{w}^\star) &\leq \sqrt{\sum\_{t \in J_2} \sum\_{i \in S_t} p_t(i \mid S_t, \mathbf{w}^\star)p_t(0 \mid S_t, \mathbf{w}^\star)} \sqrt{\sum\_{t \in J_2} \sum\_{i \in S_t} p_t(i \mid S_t, \mathbf{w}^\star)p_t(0 \mid S_t, \mathbf{w}^\star) \\| x\_{ti} \\|\_{H_t^{-1}}^2 } \\\\ &\leq \sqrt{\sum\_{t=1}^T \kappa_t^\star + \text{Reg}_T} \sqrt{ \sum\_{t=1}^T \sum\_{i \in S_t} p_t(i \mid S_t, \mathbf{w}\_{t+1})p_t(0 \mid S_t, \mathbf{w}\_{t+1}) \\| x\_{ti} \\|\_{H_t^{-1}}^2 } \\\\ &= \tilde{\mathcal{O}}\left( \sqrt{d} \cdot \sqrt{\sum\_{t=1}^T \kappa_t^\star + \text{Reg}_T} \right), \end{align*} where the second inequality holds by the definition of $J_2$ and Lemma 11 in Goyal and Perivier [24]. Hence, we get $2 \beta_T(\delta) \sum\_{t \in J_2} g_t(S_t; \mathbf{w}^\star) = \tilde{\mathcal{O}}\left( d \sqrt{\sum\_{t=1}^T \kappa_t^\star + \text{Reg}_T} \right)$. Therefore, by solving $\text{Reg}_T = \tilde{\mathcal{O}} \left( d \sqrt{\sum\_{t=1}^T \kappa_t^\star + \text{Reg}_T } + d^2/\kappa \right)$, we can conclude that $\text{Reg}_T = \tilde{\mathcal{O}}\left( d \sqrt{\sum\_{t=1}^T \kappa_t^\star} + d^2/\kappa \right)$.
Summary
This paper studies MNL bandit problem and proposes computationally efficient algorithms in both uniform and non-uniform settings. The authors present lower bounds for these two settings and show their results are minimax optimal up to logarithmic factors.
Strengths
1. The paper achieves the minimax optimal results for the MNL bandit problem in both uniform and non-uniform settings, contributing new findings to the community. 2. This paper introduces computationally efficient algorithms that enhance the computational complexity over prior works. 3. Empirical evidence provided by the authors convincingly demonstrates the effectiveness of the proposed algorithms, strengthening the paper's claims with solid experimental validation.
Weaknesses
1. My main concern is about the contribution and technical novelty of this paper. From the statistical perspective, the regret for the uniform setting does not advance beyond the results presented in Goyal and Perivier (2021) and the $\kappa$-independent bound for the non-uniform setting has been achieved in Agrawal et al. (2023) (A comparison with Agrawal et al. (2023) in the table would be beneficial for highlighting any improvement). The main contribution of this paper is the improvement of the computational complexity. However, this enhancement comes from the online parameter estimation, which is almost the same as that in Zhang and Sugiyama (2023), with only minor modifications. As MNL bandits considered in this paper and MLogB bandits are quite similar, this modification is not significant. 2. The claim that "This complexity arises because the optimistic revenue...requiring a different analysis" in Remark 2 seems overstated. The issue of assortment optimization to maximize optimistic revenue has been previously addressed by Oh and Iyengar (2021). The approach in the paper does not deviate from their method, which makes the purported contribution questionable. 3. The presentation of lower bounds for both settings to demonstrate result optimality is appreciated, yet the inclusion of a problem-dependent lower bound that illustrates the influence of the problem-specific parameter $\kappa$ would have added significant value, as seen in studies on logistic bandits.
Questions
1. Can the proposed algorithms be directly applied to achieve the optimal results for binary logistic bandits? It would be beneficial for the paper to discuss this applicability. 2. The empirical performance shown in Figure 1 suggests UCB outperforms TS in non-uniform settings, contrary to the fact that TS usually achieves better empirical performance than UCB in the literature. Moreover, though OFU-MNL+ outperforms the two other baselines, all algorithms appear to incur linear regret in specific scenarios (e.g., (N=100, K=10, d=5, Uniform R)). Could the authors provide some intuition for these phenomena?
Rating
7
Confidence
4
Soundness
3
Presentation
3
Contribution
3
Limitations
\
Additional Comments by Authors [1/2]
### **Questions** **Q1. Achieving the optimal results for binary logistic bandits** Yes, it is **explained in Lines 291-293**. When $K=1, r_{ti}=1$, and $v_0=1$, our problem can be reduced to the logistic bandit problem. Under these conditions, we achieve a regret of $\tilde{\mathcal{O}}(d\sqrt{\kappa T})$ by Corollay 1 in Zhang and Sugiyama [49]. **Q2-1. Figure 1 suggests UCB outperforms TS in non-uniform settings, contrary to the fact that TS usually achieves better empirical performance than UCB.** While TS often outperforms UCB algorithms in many bandit problems, it is NOT guaranteed to perform better. For example, even in linear bandits, the worst-case regret of TS (Agrawal and Goyal [6]) is known to be worse than that of UCB (Abbasi-Yadkori et al. [1]) as many experts would know. That is, there are instances where UCB can empirically outperform TS. Additionally, the empirical results from Oh and Iyengar [39] further demonstrate that UCB performs better than TS in MNL bandits. **Q2-2. All algorithms appear to incur linear regret in specific scenarios (e.g., (N=100, K=10, d=5, Uniform R)).** First, we would like to clarify that the regret upper bounds of the baseline algorithms (UCB-MNL and TS-MNL) are inversely proportional to $\kappa$. As we explained in Line 196 of our paper, since $1/\kappa = \mathcal{O}(K^2)$, the curvature of the regret curves of the baselines decreases as the assortment size $K$ increases. This is why their curves appear to be linear. However, it's important to note that while the regret curves of these baselines may appear linear, they are actually sub-linear, curving very slowly. This indicates that these algorithms learn at a significantly slower rate compared to our algorithm. The table included below clearly demonstrates that the regret curves are indeed sub-linear. The average cumulative regret and the increase in regret every 500 rounds under N=100, K=10, d=5, uniform rewards: | round | UCB-MNL | $\Delta$ UCB | TS-MNL | $\Delta$ TS | Ours | $\Delta$ Ours | |-------|----------------|-----------|------------|-----------|-----------|----------| | 1 | 0.044908 | | 0.046225 | | 0.033627 | | | 501 | 16.33583 | 16.290922 | 26.57288 | 26.526655 | 7.65057 | 7.616943 | | 1001 | 31.896535 | 15.560705 | 52.93464 | 26.36176 | 11.883341 | 4.232771 | | 1501 | 47.225106 | 15.328571 | 79.144988 | 26.210348 | 14.85561 | 2.972269 | | 2001 | 62.326848 | 15.101742 | 105.145026 | 26.000038 | 17.124088 | 2.268478 | | 2501 | 77.195593 | 14.868745 | 130.847381 | 25.702355 | 19.058557 | 1.934469 | | 3001 | 91.963978 | 14.768385 | 156.315643 | 25.468262 | 20.676582 | 1.618025 | Other scenarios show similar trends. --- ### **A. Technical errors in Agrawal et al. (2023) [5]** **1. Equation (16)**: $\alpha_i(\mathbf{X}_{S_t}, \theta_t, \theta^{\star}) x\_{ti} :=\mu_i(\mathbf{X}\_{S_t}^\top \theta^\star) - \mu_i(\mathbf{X}\_{S_t}^\top \theta_t)$, where $\mathbf{X}\_{S_t}$ is a design matrix whose columns are the attribute vectors $x\_{ti}$ of the items in the assortment $S_t$ and $\mu_i(\mathbf{X}\_{S_t}^\top \theta) = P_t(i \mid S_t, \theta)$. * It appears that the authors may have intended to derive this equation using a first-order exact Taylor expansion. However, in MNL bandits, this equation generally does not hold. Consider a counterexample where $x_{ti}=0$, $x_{tj} \neq 0$ for $j \neq i$, and $\theta^\star \neq \theta_t$. Then, LHS is equals to $0$. In this case, the left-hand side (LHS) equals $0$ (since $x_{ti}=0$), but the right-hand side (RHS) is not $0$, because the denominators of each $\mu_i(\mathbf{X}\_{S_t}^\top \theta^\star)$ and $\mu_i(\mathbf{X}\_{S_t}^\top \theta_t)$ differ. This equation only holds in special cases, such as when $K=1$, which corresponds to the logistic bandit case. Equation (16) serves as the foundation for the entire proof in their paper. Consequently, all subsequent results derived from it are also incorrect. **2. Cauchy-Schwarz inequality in the regret analysis (Page 46)** * When using the Cauchy-Schwarz inequality on the regret before applying the elliptical potential lemma, they indeed incur an additional $\sqrt{K}$ factor: $\sum_{t=1}^T \min \left(\sum_{i \in S_t}\\|x_{ti}\\|_{\mathbf{J}\_t^{-1}},1 \right) \leq \sqrt{KT} \sqrt{\min \left(\sum\_{i \in S_t} \\|x\_{ti}\\|\_{\mathbf{J}\_t^{-1}}^2 ,1 \right)}. $ * Hence, their regret should actually be $\tilde{\mathcal{O}}(d\sqrt{KT} + d^2/\kappa)$, which is worse than the result in our Theorem 2 (upper bound under uniform rewards) **by a factor of $K$**. --- > Continued in the next comment.
Additional Comments by Authors [2/2]
### **B. Proof of problem-dependent ($\kappa$) lower bound** In the proof of Theorem 1, both the optimal assortment $S^\star$ and an alternative assortment $\tilde{S}_t$ (only has feature vectors that maximizes the utility in $S_t$) have the same feature vectors for each assortment. Let $S^\star = \\{x,\dots,x \\}$ and $\tilde{S}_t = \\{\hat{x}, \dots, \hat{x}\\}$. Then, by Proposition D.1, we have $ \sum_{i \in S^\star} p(i \mid S^\star, \mathbf{w}^\star) - \sum_{i \in S_t} p (i \mid S_t, \mathbf{w}^\star) \geq \sum_{i \in S^\star} p(i \mid S^\star, \mathbf{w}^\star) - \sum_{i \in \tilde{S}_t} p (i \mid \tilde{S}_t, \mathbf{w}^\star) =: f(x;\mathbf{w}^\star) - f(\hat{x};\mathbf{w}^\star). $ Here, $f(x;\mathbf{w}^\star) = \frac{ K\exp(x^\top\mathbf{w}^\star ) }{v_0 + K \exp(x^\top \mathbf{w}^\star)}$ maps from $\mathbb{R}^d$ to $\mathbb{R}$. Since the input to the function $f$ is a single vector $x$, $f$ can be regarded as a logistic function. This characteristic allows us to follow the proof of Theorem 2 from Abeille et al. (2021) [4], resulting in a regret lower bound of $\Omega(d\sqrt{\kappa^\star T})$ where $\kappa^\star := \sum_{i \in S^\star} p(i \mid S^\star, \mathbf{w}^\star) p(0 \mid S^\star, \mathbf{w}^\star)$.
Thank you!
Thank you very much for kindly increasing the score. We sincerely hope that we have addressed all of your concerns and that our work’s significance is now clearer. Your thoughtful feedback has been instrumental, and we believe that the final version will be strengthened as a result.
Thank you for your response.
Thank you for your response. I appreciate that my main concerns were addressed, so I've improved my score. I'm also grateful to the author for highlighting the technical errors in the previous article. However, I still have a few technical questions regarding the paper. The analysis by Zhang & Sugiyama (2023) seems to rely heavily on the one-step distance of online mirror descent (Lemma 20 of their paper). However, I could not find the one-step distance analysis within the paper. Could you please provide more details on this?
Thanks!
Thank you once again for your positive reevaluation of our paper. We are glad that we were able to address your major concern! To answer your question: We could have used Lemma 20 from Zhang & Sugiyama (2023). However, since the **leading term of the regret upper bound remains unchanged**, we determined that the lemma was not essential and decided not to include it. First, let’s revisit Lemma 20 from Zhang & Sugiyama (2023). Notably, their bound can be improved by a factor of $\sqrt{K}$. Specifically, because $\\| \nabla \ell_t (\mathbf{w}\_t) \\|_2 \leq 2$ (rather than $\\| \nabla \ell_t (\mathbf{w}\_t) \\|_2 \leq 2\sqrt{K}$ as they suggested), we can derive $\\| \mathbf{w}\_{t+1} - \mathbf{w}\_t \\|\_{H_t} \leq \frac{\alpha}{\lambda}$ (instead of $\\| \mathbf{w}\_{t+1} - \mathbf{w}\_t \\|\_{H_t} \leq \frac{\alpha \sqrt{K}}{\lambda}$), where $\alpha = \mathcal{O}(\log K)$. With this revised version of Lemma 20, we could apply it to derive the same regret upper bound. In Line 746, by taking the absolute value of the regret, we can use a second-order Taylor expansion around $\mathbf{u}\_t$ (instead of $\mathbf{u}\_t^\star$) as follows: \begin{align*} \sum\_{t=1}^T | Q(\mathbf{u}\_t) - Q(\mathbf{u}\_t^\star) | \leq \underbrace{\sum\_{t=1}^T | \nabla Q(\mathbf{u}\_t)^\top (\mathbf{u}\_t^\star - \mathbf{u}\_t) |}\_{\text{(A)}} + \underbrace{\frac{1}{2} \sum\_{t=1}^T| (\mathbf{u}\_t^\star - \mathbf{u}\_t)^\top \nabla^2 Q(\bar{\mathbf{u}}\_t) (\mathbf{u}\_t^\star - \mathbf{u}\_t) |}\_{\text{(B)}} \end{align*} The term (A) can be bounded using a similar analysis to our proof of Theorem 2, except that we need to bound $\\| \mathbf{w}\_{t+1} - \mathbf{w}\_t\\|\_{H_t}$ instead of $\\| \mathbf{w}\_{t+1} - \mathbf{w}^\star \\|\_{H_t}$ (refer to Lines 763 and 768). Since $\\| \mathbf{w}\_{t+1} - \mathbf{w}\_t\\|\_{H_t} \leq \frac{\alpha}{\lambda} = \mathcal{O}(\frac{1}{d})$ and $\\| \mathbf{w}\_{t+1} - \mathbf{w}^\star \\|\_{H_t} \leq \beta_t(\delta) = \mathcal{O}(\sqrt{d}\log t \log K)$, applying Lemma 20 of Zhang & Sugiyama (2023) results in a tighter bound. However, we only apply Lemma 20 to non-leading terms—the second and third terms of Eq. (E.4) (Line 757). Specifically, by using Lemma 20, we can bound these terms by $\tilde{\mathcal{O}}(\frac{1}{\kappa})$ which is dominated by the bound for term (B) at $\tilde{\mathcal{O}}(\frac{d^2}{\kappa})$. Thus, the leading term of the regret upper bound remains unchanged. We hope our response addresses your question. If you have any additional questions or comments, we would be more than happy to address them.
Thank you very much.
We sincerely appreciate your decision to further increase the score. It has been a pleasure discussing our work with you. Thank you very much!
Summary
The paper closes the gap between upper and lower bounds for contextual MNL bandits over various scenarios, including for varying $v_0$ and uniform/non-uniform rewards. Furthermore, the paper proposes a computationally efficient algorithm that achieves such nearly optimal upper bound, which is validated numerically as well.
Strengths
- Clearly, very well-written - Clear-cut contributions that close all the gaps remaining in the contextual MNL bandits - Numerical verification - Various technical contributions, mainly for the analysis but also for the algorithm design (Eqn. (6))
Weaknesses
- Nothing noticeable; see questions
Questions
**Questions** - In Remark 2, the authors mention that the optimistic bonus incurs exponential computational cost. But, disregarding the computational complexity, is there any advantage of doing so from the statistical/theoretical perspective? Somewhat related, although the authors have avoided the MLE-based approach for computational complexity, does using MLE with the intuitions provided here could lead to better regret guarantees in other dependencies? - In the regret upper bounds, there is a transient term $\frac{d^2}{\kappa}$. Is this an artifact of the proof? Or is there a hidden warmup phase done implicitly by the OFU-MNL+? Then, if one is okay with incurring such transient terms anyhow, is there potential for doing even better through forced exploration-type approaches (e.g., [1,2] for logistic bandits)? - Although the $1$-boundedness of $w^\star$ is standard in MNL bandits, if we relax this to $B$-boundedness for some $B > 0$, then does this imply that $\kappa$ may scale exponentially in $B$, like logistic bandits [3]? - Can the lower bound in Theorem 1 be written as a local minimax lower bound (e.g., Theorem 2 of [3]) centered around a specific instance? This seems like a better presentation than the current representation, which seems to be a generic minimax, where the max is over all possible problem instances. Also, the lower-bound construction, although inspired by prior works on MNL bandits, resembles a bit of [3] as well. I encourage the authors to check Appendix D of [3], especially the Averaging Hammer technique, and if applicable, include some discussions on this as well. Such instance-specific local minimax lower bound may make the result stronger. **Suggestions** - In the main text, for all the theorem statements, please include (hyper)ref for where the full proof is in the Appendix. - Although a bit complex, for practitioners, it might be beneficial to include the precise constants for the $\beta_t(\delta)$ in Lemma 1 (or point to the Appendix with the constants). A follow-up question: for the experiments, do the authors use the precise parameter as specified theoretically? - Might be beneficial to move the problem setting to earlier part of the paper, but not too sure here. [1] https://arxiv.org/abs/2404.06831 [2] https://arxiv.org/abs/2202.02407 [3] https://proceedings.mlr.press/v130/abeille21a.html
Rating
9
Confidence
4
Soundness
4
Presentation
4
Contribution
4
Limitations
Yes
Thanks!
We truly appreciate your strong support for our paper! The discussions with you during this rebuttal period have been both highly valuable and genuinely enjoyable. Each of your comments has been very constructive and has helped us improve our work. Below are our responses to your additional questions. --- **Q1. Regarding the transient term $d^2/\kappa$** The transient term $d^2/\kappa$ pops up when bounding the second-order term of the regret (term (B) in Line 746), analogous to what is observed in logistic bandits as discussed by Abeille et al. (2021) [3] and Faury et al. (2020) [18]. In their work, the second-order regret term also scales with $1/\kappa$. Global information (measured through $1/\kappa$) is pushed into a second-order term that vanishes quickly. To address the question of whether an arm-set geometry-dependent transient term is possible, we believe that directly applying the proof from logistic bandits is not feasible. Extending it to our setting presents several challenges: 1. **Setting**: We would need to shift from our current setting (adversarial contexts) to a fixed-arm setting. 2. **Multiple item selection**: In Abeille et al. (2021), the tighter bound for the second-order term is largely achieved by focusing on whether $x_{\star}(\theta_\star)^\top \theta_{\star} \geq 0$ holds or not. However, in our setting, the optimal assortment includes multiple items, which makes it much more complex to divide the cases in a similar way. 3. **Lemma 9 is not applicable**: To bound the second-order term, Abeille et al. (2021) use Lemma 9, which is only valid when the input to the function $f(\cdot)$ is a scalar. Since our function $Q(\cdot)$ (Line 742) takes a $K$-dimensional vector as input, this lemma does not apply to our case. There are likely additional complexities that make it challenging to derive a bound for the second-order term that depends on the arm structure. Nonetheless, we believe this is a highly interesting direction for future research. Thank you for the intriguing question! --- **Q2. Regrading confidence sequence** Goyal and Perivier (2022) [24] also achieved a $\kappa$-free CS (See Proposition 2 in their paper). However, they constructed their CS based on the MLE, which incurs a computational cost of $\mathcal{O}(t)$ computation cost per round to estimate the parameter. More importantly, their CS is non-convex, making it intractable to compute an optimistic parameter $\tilde{\theta}\_{ti} = \arg\max\_{\theta \in \mathcal{C}\_t(\delta)}x\_{ti}^\top \theta$. We plan to compare our resulting confidence set (Lemma 1) with other works in the camera-ready version. Thank you for the constructive suggestion! --- **Q3. Explicit dependencies on $B$** We agree that assuming $B$-boundedness of the parameter norm would enhance clarity. We will update the assumption and the corresponding constant in our camera-ready version. With the $B$-boundedness assumption, the constants for the algorithms are as follows: - $\eta$: $\frac{1}{2} \log(K+1) + B + 1$ - $\lambda$: $84\sqrt{2} d \eta$ - $\beta_t(\delta)$: \begin{align*} &\sqrt{(\log(K+1)+B+1) \left( ( 3\log(1+(K+1)t) + B + 2 ) \left( \frac{17}{16}\lambda + 2\sqrt{\lambda} \log \left( \frac{2 \sqrt{1+2t}}{\delta} \right) + 16 \left( \log\left( \frac{2\sqrt{1+2t}}{\delta} \right) \right)^2 \right) + 2 + \frac{7\sqrt{6}}{6} \eta d \log \left( 1 + \frac{t+1}{2\lambda}\right) \right) + 2 \ B^2} \\\\ &= \mathcal{O}(B \sqrt{d} \log K \log t ) \end{align*}
Summary
The paper studies the contextual multinomial logit bandit problem. In this problem a learner interacts with the environment over a sequence of rounds. At each round, the learner receives features for $N$ arms and decides to select up-to $K$ of them (called an assortment) and play them. The environment might select one of these arms with a probability determined by a multinomial distribution and the learner receives a reward for the selected arm. The goal is to select the optimal assortment at each round that minimizes the cumulative regret of the algorithm. The authors design algorithms for cases when the rewards are uniform (same for each arm) and non-uniform. They also provide matching lower bounds (for large enough $T$). Finally numerical experiments are performed to demonstrate the practical performance of the algorithm.
Strengths
The authors do a great job of explaining the problem statement and prior work and position their work appropriately. I believe this is a very important direction since bandit algorithms have recently started getting popular in practical settings where the assumption of linear rewards no longer holds. Getting optimal regret guarantees for such non-linear models has gained good attention recently and the paper contributes to this in a clear non-trivial way. It's great to see that the authors prove matching lower bounds for the uniform case (for general $v_0$) and for non-uniform case (for bounded $v_0$). This adds further credibility to their algorithm and the upper bound.
Weaknesses
I am not an expert on the MNL problem but I was wondering if the algorithm offers anything new to the logistic bandit setting. Recently lot of work has happened in obtaining computationally efficient algorithms with optimal regret (independent of a problem non-linearity parameter $\kappa$). It would be good to see if anything new can be said about that setting using the results in this paper. Also, empirical comparisons on both regret and time complexity (for logistic bandit i.e. K=1 as well as larger K) can be a good addition to the paper. Minor comment - Typo on line 183. The correct definition should be $S_t^\star = \arg\max_{S\in \mathcal{S}} R_t(S, w^\star)$. My expertise in this topic is limited and I will wait to see what the other reviewers think as well.
Questions
Is the problem dependent constant $\kappa$ in line 189 same as the non-linearity $\kappa$ defined in prior work for logistic bandits (See [4,20,21]). It seems to be slightly differently defined here so I was curious to see if it meant the same at least in the logistic case.
Rating
7
Confidence
2
Soundness
3
Presentation
3
Contribution
3
Limitations
N/A
Summary
The authors consider the problem of sequentially picking assortments of items in an online manner over a horizon of $T$ rounds, where a user then selects from the items or not according to a multinomial logit model with a fixed unknown preference vector. The items are represented as (known) feature vectors which can change adversarially from round to round. The authors prove tighter cumulative regret lower bounds for both uniform and non-uniform cases and propose an algorithm with matching upper bounds. The authors account for the probability of a user not choosing from the given options in the bounds. The authors also run experiments to compare their algorithm to baselines.
Strengths
### Major - Improved lower bounds for contextual MNL bandits in the uniform-reward setting, accounting for the impact of the probability of the null action. - improved lower bounds also in the non-uniform reward setting. - A tractable algorithm is proposed with matching regret upper bounds for both uniform and non-uniform reward setting ### Minor - The authors include experiments for non-uniform rewards, showing significant improvements in both run-time and cumulative regret for included baselines. - Good discussions and remarks on effects of problem setup, such as $v_0$ and whether rewards are uniform or not on regret bounds, and relations with prior works (among those discussed to some length). - Overall I found the writing to be good. Table 1 is helpful.
Weaknesses
### Minor 1. Zhang and Luo “Contextual Multinomial Logit Bandits with General Value Functions” [48] is only mentioned once in line 128 in a sentence about past works claiming $K$-independent regret lower bounds while not accounting for $v_0$ (with the next sentence pointing out issue that several lower bounds used $v_0 = K$. However, in [48] they propose algorithms and show regret bounds for a harder problem (adversarial contexts and adversarial rewards and for more general settings than MNL models) that avoid $\kappa$ dependence in the leading term, though for the simpler problem studied in the current paper may have loose assortment size $K$ dependence. In [48] it looks to me like they consider $v_0=1$ not $v_0=K$ as implied by the current paper. Thus, while [48] is cited, to me it seems to be improperly cited and the results should be more thoroughly discussed, and unless some justification should be included in Table 1. 2. State of the art upper bounds for non-contextual MNL are not discussed. Non-contextual MNL lower bounds are included in Table 1 and discussed, but unless I overlooked it did not see anything on upper bounds, even from papers like Agrawal et al. (2019) “MNL-bandit...” [8] that were discussed for lower bounds. (Or do the contextual upper bounds with $d=N$ recover them in current state of the art?) 3. Agrawal et al. “A tractable ..” 2023 [5] is cited in a few places regarding the problem setting (like in line 186 for assumptions 1 and 2, line 282 for $v_0$, …), but not included in Table 1 or discussed in detail. They achieve improved regret upper bound dependence on $\kappa$ from prior works using a reportedly tractable algorithm. Agrawal et al. [5] consider a (contextual) combinatorial assortment problem using an MNL model with adversarial contexts and uniform rewards and $v_0 = 1$. 4. Choi et al. “Cascading Contextual Assortment Bandits” in NeurIPS 2023 is not cited. How would their results compare? Their regret upper bound (specialized to the non-cascading setting you consider) looks competitive for $v_0=1$ and uniform reward setting. Another cascading assortment paper by Cao and Sun “Tiered Assortment: Optimization and Online Learning” in Management Science is also not cited, though they acknowledge in their Remark 2 that in the special case of a single tier, their result matches Agrawal et al. (2019) “MNL-bandit...” [8]. 5. The authors consider the parameter vector $\textbf{w}$ bounded by $1$ instead of bounded by a known constant $S$ like in previous works (such as Agrawal et al. 2023 [5] and Lee et al. 2024 [32]). As pointed out by Leet et al. 2024 [32], “These quantities [$\kappa$] can scale exponentially in S in the worst-case (Faury et al., 2020).” How would the results be impacted accounting for such a known bound instead of setting it to 1? 6. A clearer discussion on the computational complexity of the methods listed as “intractable” (in particular Goyal and Perivier 2022 [24]) would be better, both worst-case and (if not included in experiments) conjecture whether where they would have been in Fig. I.1 (eg even for those instances would it have been so slow as to be off the charts?). ### Very Minor - [24] cites an arxiv version of a NeurIPS 2022 paper
Questions
(some questions are included above in comments made in “Weaknesses”)
Rating
7
Confidence
3
Soundness
3
Presentation
3
Contribution
2
Limitations
Yes
Additional Comments by Authors [1/2]
### **A. Technical errors in Agrawal et al. (2023) [5]** **1. Equation (16)**: $\alpha_i(\mathbf{X}_{S_t}, \theta_t, \theta^{\star}) x\_{ti} :=\mu_i(\mathbf{X}\_{S_t}^\top \theta^\star) - \mu_i(\mathbf{X}\_{S_t}^\top \theta_t)$, where $\mathbf{X}\_{S_t}$ is a design matrix whose columns are the attribute vectors $x\_{ti}$ of the items in the assortment $S_t$ and $\mu_i(\mathbf{X}\_{S_t}^\top \theta) = P_t(i \mid S_t, \theta)$. * It appears that the authors may have intended to derive this equation using a first-order exact Taylor expansion. However, in MNL bandits, this equation generally does not hold. Consider a counterexample where $x_{ti}=0$, $x_{tj} \neq 0$ for $j \neq i$, and $\theta^\star \neq \theta_t$. Then, LHS is equals to $0$. In this case, the left-hand side (LHS) equals $0$ (since $x_{ti}=0$), but the right-hand side (RHS) is not $0$, because the denominators of each $\mu_i(\mathbf{X}\_{S_t}^\top \theta^\star)$ and $\mu_i(\mathbf{X}\_{S_t}^\top \theta_t)$ differ. This equation only holds in special cases, such as when $K=1$, which corresponds to the logistic bandit case. Equation (16) serves as the foundation for the entire proof in their paper. Consequently, all subsequent results derived from it are also incorrect. **2. Cauchy-Schwarz inequality in the regret analysis (Page 46)** * When using the Cauchy-Schwarz inequality on the regret before applying the elliptical potential lemma, they indeed incur an additional $\sqrt{K}$ factor: $\sum_{t=1}^T \min \left(\sum_{i \in S_t}\\|x_{ti}\\|_{\mathbf{J}\_t^{-1}},1 \right) \leq \sqrt{KT} \sqrt{\min \left(\sum\_{i \in S_t} \\|x\_{ti}\\|\_{\mathbf{J}\_t^{-1}}^2 ,1 \right)}. $ * Hence, their regret should actually be $\tilde{\mathcal{O}}(d\sqrt{KT} + d^2/\kappa)$, which is worse than the result in our Theorem 2 (upper bound under uniform rewards) **by a factor of $K$**. --- ### **B. Problem-dependent bounds** **1. Upper bound** By adapting Theorem 2 from Faury et al. (2022) [21] to the multinomial and online parameter setting, we can achieve a regret upper bound of $\tilde{\mathcal{O}}\left( d \sqrt{\sum_{t=1}^T \kappa_t^\star} + d^2/\kappa \right)$, where $\kappa_t^\star = \sum_{i \in S_t^\star} p_t(i \mid S_t^\star, \mathbf{w}^\star)p_t(0 \mid S_t^\star, \mathbf{w}^\star)$. **Proof of the upper bound**: We start the proof from line 748 in the proof of Theorem 2. \begin{align*} \sum\_{t=1}^T \nabla Q(\mathbf{u}\_t^\star)^\top (\mathbf{u}\_t - \mathbf{u}\_t^\star) \leq 2 \beta_T(\delta) \sum\_{t=1}^T \sum\_{i \in S_t} p_t(i \mid S_t, \mathbf{w}^\star)p_t(0 \mid S_t, \mathbf{w}^\star) \\| x\_{ti} \\|_{H_t^{-1}}. \end{align*} Let $g_t(S ; \mathbf{w}):= \sum\_{i \in S} p_t(i \mid S, \mathbf{w})p_t(0 \mid S, \mathbf{w}) \\| x\_{ti} \\|_{H_t^{-1}}$. Let $J_1 = \\{ t \in [T] \mid \sum\_{i \in S_t} p_t(i \mid S_t, \mathbf{w}^\star)p_t(0 \mid S_t, \mathbf{w}^\star) \geq \sum\_{i \in S_t} p_t(i \mid S_t, \mathbf{w}\_{t+1})p_t(0 \mid S_t, \mathbf{w}\_{t+1})\\\}$ and $J_2 = [T] \setminus J_1$. Thus, we get \begin{align*} \text{RHS} = 2 \beta_T(\delta) \sum\_{t=1}^T g_t(S_t; \mathbf{w}^\star) = 2 \beta_T(\delta) \sum\_{t \in J_1} g_t(S_t; \mathbf{w}^\star) + 2 \beta_T(\delta) \sum\_{t \in J_2} g_t(S_t; \mathbf{w}^\star). \end{align*} To bound $\sum_{t \in J_1} g_t(S_t; \mathbf{w}^\star)$, by the mean value theorem, we get \begin{align*} \sum\_{i \in J_1} g_t(S_t; \mathbf{w}^\star) = \sum\_{i \in J_1} g_t(S_t; \mathbf{w}\_{t+1}) + \sum\_{i \in J_1} \nabla\_{\mathbf{w}} g_t(S_t; \bar{\mathbf{w}}_t)^\top (\mathbf{w}^\star - \mathbf{w}\_{t+1}), \end{align*} where $\bar{\mathbf{w}}_t$ is the convex combination of $\mathbf{w}^\star$ and $\mathbf{w}\_{t+1}$. The first term can be bound by \begin{align*} \sum\_{t \in J_1} g_t(S_t; \mathbf{w}\_{t+1}) &\leq \sqrt{\sum\_{t\in J_1} \sum\_{i \in S_t} p_t(i \mid S_t, \mathbf{w}\_{t+1})p_t(0 \mid S_t, \mathbf{w}\_{t+1})} \sqrt{\sum\_{t \in J_1} \sum\_{i \in S_t} p_t(i \mid S_t, \mathbf{w}\_{t+1})p_t(0 \mid S_t, \mathbf{w}\_{t+1}) \\| x_{ti}\\|\_{H_t^{-1}}^2 } \\\\ &\leq \sqrt{\sum\_{t\in J_1} \sum\_{i \in S_t} p_t(i \mid S_t, \mathbf{w}^\star)p_t(0 \mid S_t, \mathbf{w}^\star)} \cdot \tilde{\mathcal{O}}( \sqrt{d} ) \leq \sqrt{\sum\_{t=1}^T \kappa_t^\star + \text{Reg}\_T} \cdot \tilde{\mathcal{O}}( \sqrt{d} ) , \end{align*} where the second-to-the last inequality holds by the definition of $J_1$ and the elliptical potential lemma in our paper, and the last inequality holds by Lemma 11 in Goyal and Perivier [24] with $\kappa_t^\star := \sum\_{i \in S_t^\star} p_t(i \mid S_t^\star, \mathbf{w}^\star)p_t(0 \mid S_t^\star, \mathbf{w}^\star)$. Moreover, the second term can be bounded by >Continued in the next comment.
Additional Comments by Authors [2/2]
\begin{align*} \left|\sum\_{i \in J_1}\nabla_{\mathbf{w}} g_t(S_t; \bar{\mathbf{w}}\_t)\top (\mathbf{w}^\star - \mathbf{w}\_{t+1}) \right| &=\Bigg|\sum\_{t \in J_1} p_t(0 \mid S_t, \bar{\mathbf{w}}\_t) \sum_{i \in S_t}p_t(i \mid S_t, \bar{\mathbf{w}}\_t) x\_{ti}^\top (\mathbf{w}^\star - \mathbf{w}\_{t+1}) \\| x_{ti} \\|\_{H_t^{-1}} - 2 p_t(0 \mid S_t, \bar{\mathbf{w}}_t) \sum\_{i \in S_t}p_t(i \mid S_t, \bar{\mathbf{w}}\_t) \\| x\_{ti} \\|\_{H_t^{-1}} \sum\_{j \in S_t}p_t(j \mid S_t, \bar{\mathbf{w}}\_t) x\_{tj}^\top (\mathbf{w}^\star - \mathbf{w}\_{t+1}) \Bigg| \\\\ &\leq 3 \beta\_{T}(\delta) \sum\_{t=1}^T \max\_{i \in S_t} \\| x\_{ti} \\|\_{H_t^{-1}}^2 = \tilde{\mathcal{O}}(d^{3/2}/\kappa). \end{align*} Hence, we get $2 \beta_T(\delta) \sum\_{t \in J_1} g_t(S_t; \mathbf{w}^\star) = \tilde{\mathcal{O}}\left( d \sqrt{\sum\_{t=1}^T \kappa\_t^\star + \text{Reg}_T} + d^{2}/\kappa \right)$. Now, we bound $\sum\_{t \in J_2} g_t(S_t; \mathbf{w}^\star)$. \begin{align*} \sum\_{t \in J_2} g_t(S_t; \mathbf{w}^\star) &\leq \sqrt{\sum\_{t \in J_2} \sum\_{i \in S_t} p_t(i \mid S_t, \mathbf{w}^\star)p_t(0 \mid S_t, \mathbf{w}^\star)} \sqrt{\sum\_{t \in J_2} \sum\_{i \in S_t} p_t(i \mid S_t, \mathbf{w}^\star)p_t(0 \mid S_t, \mathbf{w}^\star) \\| x\_{ti} \\|\_{H_t^{-1}}^2 } \\\\ &\leq \sqrt{\sum\_{t=1}^T \kappa_t^\star + \text{Reg}_T} \sqrt{ \sum\_{t=1}^T \sum\_{i \in S_t} p_t(i \mid S_t, \mathbf{w}\_{t+1})p_t(0 \mid S_t, \mathbf{w}\_{t+1}) \\| x\_{ti} \\|\_{H_t^{-1}}^2 } \\\\ &= \tilde{\mathcal{O}}\left( \sqrt{d} \cdot \sqrt{\sum\_{t=1}^T \kappa_t^\star + \text{Reg}_T} \right), \end{align*} where the second inequality holds by the definition of $J_2$ and Lemma 11 in Goyal and Perivier [24]. Hence, we get $2 \beta_T(\delta) \sum\_{t \in J_2} g_t(S_t; \mathbf{w}^\star) = \tilde{\mathcal{O}}\left( d \sqrt{\sum\_{t=1}^T \kappa_t^\star + \text{Reg}_T} \right)$. Therefore, by solving $\text{Reg}_T = \tilde{\mathcal{O}} \left( d \sqrt{\sum\_{t=1}^T \kappa_t^\star + \text{Reg}_T } + d^2/\kappa \right)$, we can conclude that $\text{Reg}_T = \tilde{\mathcal{O}}\left( d \sqrt{\sum\_{t=1}^T \kappa_t^\star} + d^2/\kappa \right)$. --- **2. Lower bound** We can also derive a regret lower bound of $\Omega(d\sqrt{\kappa^\star T})$ by applying Theorem 2 from Abeille et al. (2021). **Proof of the lower bound**: In the proof of Theorem 1, both the optimal assortment $S^\star$ and an alternative assortment $\tilde{S}_t$ (only has feature vectors that maximizes the utility in $S_t$) have the same feature vectors for each assortment. Let $S^\star = \\{x,\dots,x \\}$ and $\tilde{S}_t = \\{\hat{x}, \dots, \hat{x}\\}$. Then, by Proposition D.1, we have \begin{align*} \sum_{i \in S^\star} p(i \mid S^\star, \mathbf{w}^\star) - \sum_{i \in S_t} p (i \mid S_t, \mathbf{w}^\star) \geq \sum_{i \in S^\star} p(i \mid S^\star, \mathbf{w}^\star) - \sum_{i \in \tilde{S}_t} p (i \mid \tilde{S}_t, \mathbf{w}^\star) =: f(x;\mathbf{w}^\star) - f(\hat{x};\mathbf{w}^\star). \end{align*} Here, $f(x;\mathbf{w}^\star) = \frac{ K\exp(x^\top\mathbf{w}^\star ) }{v_0 + K \exp(x^\top \mathbf{w}^\star)}$ maps from $\mathbb{R}^d$ to $\mathbb{R}$. Since the input to the function $f$ is a single vector $x$, $f$ can be regarded as a logistic function. This characteristic allows us to follow the proof of Theorem 2 from Abeille et al. (2021) [4], resulting in a regret lower bound of $\Omega(d\sqrt{\kappa^\star T})$.
Thanks to the authors for the detailed response. I have read the rebuttal and decided to increase my score. I do not have further questions.
Thanks!
We sincerely appreciate your decision to increase the score. Your valuable and constructive comments will greatly contribute to strengthening the final version of our paper. Thank you for the insightful and enjoyable discussion.
Thank you for your detailed responses. I'm quite happy that the lower bound holds in a local minimax sense, which I believe is a much stronger notion for claiming instance-wise optimality of the algorithms. All my questions and concerns have been addressed, and after reading through other reviews, other significances of this paper (not requiring the knowledge of $\kappa$ for the algorithm, instance-specific upper/lower bounds available, additional experiments) have come to my attention. Thus, I'm further raising the score and willing to advocate strongly for the paper. Congratulations on the nice work! Some additional questions/suggestions: - Exactly where in the proof is the transient term $d^2 / \kappa$ popping up? Could one hope for an arm-set geometry-dependent transient term, as in the "detrimental arms" of Abeille et al. (2021)? - I don't think this was mentioned properly in the paper. Is the obtained confidence sequence (CS) the first $\kappa$-free CS in contextual MNL bandits? If time allows, for the camera ready (not the rebuttal), it would be interesting to see the resulting CS at the final stage and compare it to existing CSs. - For the camera-ready ver, I would like to see explicit dependencies on $B$ as well, with the more general assumption. Also, under the $B$-boundedness, would all the constants for the algorithm ($\lambda, \eta, \beta_t(\delta)$) as well as the regret also depend on $B$?
Decision
Accept (poster)