Nearly Minimax Optimal Regret for Multinomial Logistic Bandit

We are delighted that you enjoyed reading our paper and appreciated the value of our contributions. Thank you very much for your valuable feedback. Based on your detailed and insightful suggestions, we will make further improvements to our paper.

Regarding Assumption 2

We would like to clarify that the existence of a non-zero $\kappa$ in our Assumption 2 should NOT be considered a weakness. It is important to note that $\kappa$ is always non-zero, as all MNL probabilities are non-zero for bounded feature vectors and bounded parameters, and $\kappa$ represents the minimum value of the product of two MNL probabilities. Thus, it is more appropriate to "define" $\kappa$ rather than assuming its existence. In Goyal and Perivier (2021), $\kappa$ is also defined rather than assumed. For clarity, we will revise Assumption 2 to be a Definition in our final version.

Moreover, this is a common assumption in logistic, MNL, and generalized linear model (GLM) bandits, and should NOT be considered a unique limitation of our work.

More interestingly, although $\kappa$ can be exponentially small, our algorithm does not need to know $\kappa$. And we avoid the $\kappa$-dependence in the leading term of our regret analysis, making our algorithm much more practical.

Problem-dependent regret bounds

It turns that problem-dependent upper and lower bounds under uniform rewards are achievable. By making some modifications to our results, we can easily achieve this.

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)$. See Section A in the comment below for the proof.

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).

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})$.

Suggestions

1. Introducing Section 4 before Section 3: That’s a great suggestion. Thank you for your input. We will incorporate these changes into the final version.

2. More discussion on (1) why proving the new lower and upper bounds is non-trivial; (2) providing some proof outlines for the key steps used in the proofs: Due to the page limit, we have briefly outlined the technical novelties used in each proof in the discussions section of the main paper, while providing more comprehensive details in the Appendix. If we receive an extra page for the camera-ready version, as you suggested, we will expand the discussions to further emphasize the importance of our bounds and elaborate on the key steps used in the proofs.

3. Clear definition of $v_0$: The utility for the outside option $v_0$ is the attraction parameter for not choosing any item, and it is used to construct the MNL probability. For better presentation, we will include a reference to the definition of MNL probabilities (Eq.1) when we first introduce the term $v_0$ and provide additional explanation about $v_0$.

4. The meaning of "the set of items $[N]$ can vary over time" (Line 162): The statement indicates that we allow for the entry of new items into the market or the removal of existing items over time, which could also lead to changes in the total number of items, denoted as $N_t$. For clarity, we need to define the item set at time $t$ as $\mathcal{I_t}:= \\{ i_{t1}, \dots, i_{tN_t} \\}$. Thus, the item set $\mathcal{I_t}$ can vary over time. Thank you for pointing this out. We will clarify this notation in the final version of our paper.

A. Proof of problem-dependent upper bound

We start the proof from line 748 in the proof of Theorem 2.

$

\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}}.

$

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

$

\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).

$

To bound $\sum_{t \in J_1} g_t(S_t; \mathbf{w}^\star)$, by the mean value theorem, we get

$

\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}),

$

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

$

\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} ) ,

$

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

$

\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).

$

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)$.

$

\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),

$

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)$.

We appreciate your time to review our paper and your feedback. We would like to clarify some of the possible misunderstandings regarding our main contributions. Our main contributions are to establish the first minimax regret for MNL bandits, along with providing several novel insights related to variables such as $v_0$ and reward structures. We strongly believe that our results significantly advance what have been knwon in the field of MNL bandits. We will address your feedback point by point below. We sincerely hope to clarify any misunderstandings.

Regarding our main contributions

Our main contribution is NOT the improvement of computational complexity (although it is still an advantage of our proposed method). While we employ the online parameter estimation adapted from Zhang and Sugiyama [47], it is important to note that new analyses based on improved self-concordant-like properties and considering varying assortment sizes are introduced in our work.

We clearly emphasize that our main constributions are closing the gap between the upper and lower bounds in contextual MNL bandits for the first time and proposing a nearly minmax optimal algorithm. Additionally, we believe it is a significant and novel insight that the regret: 1) varies depending on the value of $v_0$ and 2) is influenced by the reward structure (uniform versus non-uniform), and 3) can improve as the assortment size $K$ increases under uniform rewards. Our contributions can be summarized as follows:

1. First minimax results in terms of $d,T,K$ and even $v_0$
2. First proofs demonstrating how regret varies with $v_0$ and reward structure
3. First lower bound under non-uniform rewards
4. First tractable $\kappa$-free uppder bound under non-uniform rewards
5. Adaptation of the online parameter estimation while maintaining the above regret bound

Each of our results tackles distinct non-trivial challenges, which we have successfully resolved in our paper. For instance, we have enhanced the self-concordance-like properties and the elliptical potential method, and introduced novel "centralized features" to prove the upper bound for non-uniform rewards. Please refer to the discussions for each theorem for more details.

Furthermore, our regret bound (Theorem 2) is a clear improvement over those presented by Goyal and Perivier (2021) and Agrawal et al. (2023).

• vs Goyal and Perivier (2021) [24]: We have improved upon the regret results of Goyal and Perivier (2021) by a factor of $K$: reducing it from $\tilde{\mathcal{O}}(d\sqrt{KT} + d^2K^4/\kappa )$ (let $\kappa^\star = \mathcal{O}(1/K)$ in the leading term) to $\tilde{\mathcal{O}}(d\sqrt{T/K} + d^2/\kappa )$. This advancement was achieved by enhancing the self-concordant-like property of the loss function (Proposition C.1) and refining the elliptical potential lemma (Lemma E.2). Moreover, we significantly improved the regret associated with the transient term, reducing it from $d^2K^4/\kappa$ to $d^2/\kappa$, by utilizing an improved bound for the second derivative of the revenue (Lemma E.3). For further details, please refer to the discussion of Theorem 2 in our paper.

• vs Agrawal et al. (2023) [5]: In fact, their paper contains significant technical errors (refer Section A in the comments below), rendering a direct comparison to our work meaningless. This is the main reason we initially chose not to compare our results with theirs. Nevertheless, in response to requests from some reviewers, we will consider including a discussion about this in our camera-ready version. Even if all errors were corrected, our result (Theorem 2) still shows an improvement over theirs in terms of $K$. Agrawal et al. (2023) considered a uniform rewards setting (with $v_0=1$) and achieved a regret of $\tilde{\mathcal{O}}(d\sqrt{T} + d^2/\kappa)$. However, the corrected regret should be $\tilde{\mathcal{O}}(d\sqrt{KT} + d^2/\kappa)$).

Remark 2 is intended solely for comparing our setting with that of Zhang and Sugiyama [47].

The purpose of Remark 2 is to explain that our setting fundamentally differs from those described by Zhang and Sugiyama [47], necessitating a different analysis. Therefore, this distinction should NOT be viewed as a weakness. Again, our main contribution is proving the first minimax results in MNL bandits.

Problem-dependent ($\kappa$) lower bound

The main goal of this paper is to explicitly show how the values of $K$ and $v_0$ affect the regrets (both upper and lower bounds). To clearly demonstrate the dependency of regret on these values, we have presented the results in terms of $K$ and $v_0$, rather than $\kappa$.

As per your request, we believe that a problem-dependent lower bound can be easily derived from our intermediate results. In the proof of Theorem 1, both the optimal assortment $S^\star$ and an alternative assortment $\tilde{S}_t$ (which only includes feature vectors that maximizes the utility in $S_t$) have the same feature vectors for each assortment. Given that the input to the MNL probability function is a single feature vector, our problem can be reduced to the logistic bandit problem. Subsequently, using similar analyses to those in the proof of Theorem 2 from Abeille et al. (2021) [4], we can derive 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)$. See Section B in the comments below for more detailed proof.

We are more than happy to include this lower bound. However, we do NOT believe that not stating the problem-dependent lower bound should be considered a weakness, as our focus is to show the regret dependence on $K$ and $v_0$.

Due to space limitations, we will address your questions in the following comments.

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)$.

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:

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.

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:

$

\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)}}

$

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.

We sincerely appreciate your decision to further increase the score. It has been a pleasure discussing our work with you. Thank you very much!

Thank you very much for your positive evaluation of our paper and for your insightful and valuable feedback. Each question you raised is an intriguing research topic, shedding light on new areas for future study.

Advantage of optimistic bonus

First, we want to clarify that the simple adaptation of Zhang and Sugiyama [49] to our method incurs "exponential computational cost" -- this is NOT an inherent drawback of our method. To the best of our knowledge, the adaptation of an optimistic bonus, as done in Zhang and Sugiyama [49], to our method does not provide any statistical advantage, despite the exponential computation cost.

Does using MLE with the intuitions provided here could lead to better regret guarantees in other dependencies?

To the best of our knowledge, given that our regret upper bound is minimax optimal (up to logarithmic factors), we believe that the use of MLE may not improve our regret bound polynomially. However, it might be possible to affect the bound logarithmically, which could be of future interest.

Regarding $d^2/\kappa$ and the potential for forced exploration-type approaches

The term $d^2/\kappa$ is an "artifact" of the proof, resulting from the second-order Taylor expansion of the regret. We do not have any warm-up phase or forced exploration in the algorithm. Hence, we are not sure whether forced exploration-type approaches can be beneficial. Based on your feedback, we considered adding an initial/intermediate forced-sampling step, but we do not believe the regret can be improved (in our current analysis). This would be an interesting area for future work.

If we relax the bound of $\\|\mathbf{w}^\star\\|_2$ to $B$-boundedness for some $B>0$, then does this imply that $\kappa$ may scale exponentially in $B$, like logistic bandits [3]?

Yes, by the deifinition, $\kappa$ is affected by $B$. Specficially, $1/\kappa$ (which appears in the lower-order term in our upper bounds) scales with $\exp(B)$.

Instance-specific local minimax lower bound

As you suggested, we have checked the Averaging Hammer technique and found that an instance-dependent lower bound is indeed achievable. Thank you very much for your valuable feedback. Your insights have greatly strengthened our paper!

We can achieve a regret lower bound of $\Omega(d\sqrt{\kappa^\star T})$ by applying Theorem 2 from Abeille et al. (2021), where $\kappa^\star := \sum_{i \in S^\star} p(i \mid S^\star, \mathbf{w}^\star) p(0 \mid S^\star, \mathbf{w}^\star)$.

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})$. We will include this result in our final paper.

Suggestions

We appreciate all your suggestions and will incorporate them into the paper as you proposed.

To answer your additional question about whether we used precise parameters in the experiments: yes, we used the exact values.

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)$:

$

&\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 )

$

Thank you for acknowledging the value of our work and providing a positive evaluation. We will address your questions below and make improvements to our paper based on your suggestions.

Anything new to the logistic bandit

There are interesting points that can be said about the logistic bandit setting:

1. The MNL bandit is better than the logistic bandit (under uniform rewards).
According to Theorem 2 in our paper, a large $K$ can be beneficial under uniform rewards. This suggests that in recommendation systems, it is advantageous to recommend multiple items (MNL bandit) rather than just a single item (logistic bandit). This aligns with the intuition that offering multiple items allows us to gather more information from user feedback. However, in real-world scenarios, offering a large assortment might lead to user fatigue. It would be interesting for future research to consider this user fatigue and determine an appropriate size of the assortment $K$.

2. As value of the utility for outside option $v_0$ increases, both the upper and lower bounds of regret for the logistic bandit decrease.
When $K=1$, our setting simplifies to the logistic bandit scenario. In this case, the upper and lower bounds are $\tilde{\mathcal{O}}(d\sqrt{T/v_0})$ and $\Omega(d\sqrt{T/v_0})$ respectively. This highlights an interesting aspect about how the value of $v_0$ influences the regrets in the logistic bandit.

Additional empirical comparison

Following your suggestion, we have conducted additional experiments for the logistic bandit case (K=1) and cases with larger $K$ ($K=20, 30$). See the "global" response above. These additional results also corroborate our theoretical claims. Particularly, under uniform rewards, we observed that regret decreases as $K$ increases, aligning with Theorems 1 and 2. In contrast, under non-uniform rewards, regret remains unchanged regardless of changes in $K$, consistent with Theorems 3 and 4.

We are pleased to provide these additional results that further substantiate the claims in our paper. Thank you very much!

Typo

Thank you very much for identifying the typo. We will make the necessary correction and ensure it is reflected in the final version of the paper. Your attention to detail is greatly appreciated.

Thank you very much for your insightful and valuable feedback. As we start our discussition, we first would like to ask for your patience for our lengthy responses. We have much to share as we have genuinely appreciated your feedback and look forward to our discussion with you! We will ensure that all the following discussions are included in our final version.

Regading Zhang and Luo (2024)

First, we would like to clarify that our setting also considers adversarial contexts and adversarial rewards. In our work, the term "the non-uniform rewards" is equivalent to the adversarial rewards. Thus, apart from the fact that Zhang and Luo (2024) [48] use a "general value function", other problem settings in [48] are not necessarily harder than ours.

Even though their tightest regret bound (Corollary 17) $\tilde{\mathcal{O}}(K^{2.5}\sqrt{dNT})$ avoids dependence on $\kappa$ based on the general value function, their regret still scales with $K$ and the number of items $N$. Moreover, as they mentioned in their paper, there is no efficient way to implement the algorithm.

To clarify, in Line 128, our point in citing [48] was to emphasize that previous studies' oversight of $v_0$'s impact on regret lower bounds has caused substantial confusion in the field. They stated that $\Omega(\sqrt{NT})$ in the non-contextual setting is optimal; however, this claim only holds true when $v_0=\Theta(K)$.

Upper bounds for non-contextual MNL bandits

We plan to discuss the upper bounds in the non-contextual setting to clearly illustrate how previous studies have derived regret bounds under varying conditions, such as different $v_0$ values and reward structures. For instance, Agrawal et al. (2019) achieved an $\tilde{\mathcal{O}}(\sqrt{NT})$ upper bound with "$v_0=1$ and non-uniform rewards". However, the known tightest lower bound, $\Omega(\sqrt{NT})$, was proven under settings of "$v_0=K$ and uniform rewards".

Comparison to Agrawal et al. (2023)

In fact, their paper contains significant technical errors (see Section A in the comments below), rendering a direct comparison to our work meaningless. This is the main reason we initially chose not to compare our results with theirs.

Even if all errors were corrected, our result (Theorem 2) still shows an improvement over theirs in terms of $K$. Agrawal et al. (2023) considered a uniform rewards setting (with $v_0=1$) and achieved a regret of $\tilde{\mathcal{O}}(d\sqrt{T} + d^2/\kappa)$. However, the corrected regret should be $\tilde{\mathcal{O}}(d\sqrt{KT} + d^2/\kappa)$.

Comparison to cascading assortment problems

Recently, both works have considered the cascading assortment bandit problem, which encompasses the MNL bandit problem as a special case where the cascading length is $1$. However, these works do not encompass our results for the following reasons.

• vs Choi et al. (2023): They consider uniform rewards, and achieve a regret upper bound of $\tilde{\mathcal{O}}(d\sqrt{T})$, which avoids dependence on both the cascading length and $\kappa$ in the leading term. When the cascading length is $1$, our result (Theorem 2) improves upon theirs by a factor of $\sqrt{K}$. Moreover, their computation cost per round is $\mathcal{O}(t)$ since they employ MLE to estimate the parameter.
• vs Cao and Sun (2023): They consider non-uniform rewards, and achieve a regret upper bound of $\tilde{\mathcal{O}}(h^2d\sqrt{MT})$, where $M$ is the cascading length and $h \geq \frac{p(i \mid S, \mathbf{w})}{p(i \mid S, \mathbf{w'})}$ for all $\mathbf{w}, \mathbf{w}' \in \mathcal{W}$, $S\in \mathcal{S}$, and $i \in S \cup \{0\}$. However, their regret bound still suffers from a harmful dependence on $h^2$, which can be exponentially large.

What happens if $\\|\mathbf{w}\\|_2 \leq B$? (+ problem-dependent bounds)

When $\\|\mathbf{w}\\|_2 \leq B$ (we use $B$ instead of $S$ to avoid notational overlap), the confidence bound $\beta_t(\delta)$ is $\tilde{\mathcal{O}}(B \sqrt{d})$. Consequently, the regret upper bounds are as follows:

• Uniform rewards: $\tilde{\mathcal{O}}(B e^{B} \frac{\sqrt{v_0 K}}{v_0 + K} d \sqrt{T})$. It's important to note that one of our main goals is to explicitly demonstrate the regret depends on $K$ and $v_0$. In deriving such a result, the dependence on $e^B$ is unavoidable to our best knowledge. Note that for the instance-dependent regret, the regret bound does not depend on $e^B$ (see below).
• Non-uniform rewards: $\tilde{\mathcal{O}}(B d \sqrt{T})$.

And the regret lower bounds remain the same, because we can always construct an instance where $\\| \mathbf{w}^\star\\|_2 \leq 1$ even if $B \gg 1$. Note that a small norm of $\mathbf{w}^\star$ typically indicates a more challenging instance, as it becomes harder to identify the optimal arm. Overall, our upper and lower bounds in terms of $K$, $d$ and $T$ (and $v_0$) are still tight, maintaining the (near) minimax optimality in terms of those problem parameters, which is our main focus.

Moreover (as per other reviewers' request), it turns that instance-dependent upper and lower bounds under uniform rewards (without dependence on $e^B$) are achievable. By making some modifications to previous results, we can easily achieve this. See Section B in the comments below for the proofs.

Computational complexity of Goyal and Perivier (2022)

The computational bottleneck of Goyal and Perivier (2022) [24] is to find an optimistic parameter $\tilde{\theta}\_t = \arg\max\_{\theta \in \mathcal{C}(\delta)} x\_{ti}^\top \theta$. However, since the confidence set $\mathcal{C}(\delta)$ is non-convex, computing $\tilde{\theta}_t$ is extremely expensive, and the worst-case cost is not well-defined. A possible solution could be a convex relaxation, as suggested by Proposition 3 in Abeille et al. (2021) [4], though exploring this is beyond the scope of our work.

$

\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).

$

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)$.

$

\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),

$

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

$

\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})$.

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.

$

\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}}.

$

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

$

\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).

$

To bound $\sum_{t \in J_1} g_t(S_t; \mathbf{w}^\star)$, by the mean value theorem, we get

$

\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}),

$

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

$

\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} ) ,

$

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.