True Impact of Cascade Length in Contextual Cascading Bandits

We sincerely thank the reviewer for the thoughtful and detailed comments on our work. Your feedback has greatly helped us refine and strengthen the paper.

1. Discussion of Regularity Conditions

Firstly, Assumption 5.1 is without loss of generality: any raw feature vector can be rescaled to lie inside the unit ball before learning, and relaxing the parameter norm bound to $S$ merely multiplies the theoretical regret by $S^{3/2}$ factor.

Secondly, we strongly believe that the existence of a non-zero $\kappa$ should NOT be viewed as a weakness of our paper, since $\kappa$ is always non-zero as long as the features and parameter vectors are bounded. In the logistic bandit literature, it is standard practice to define $\kappa$ explicitly—rather than assume it—based on problem parameters (e.g., Equation (2) of Faury et al., 2020 [1]). Therefore, we believe it is more appropriate to formally define $\kappa$ rather than assume its non-zeroness. For clarity, we will revise Assumption 5.3 to be a Definition in our final version.

Lastly, we conduct additional experiments on the MovieLens-$100K$ benchmark: reducing $\kappa$ from $0.1$ to $0.01$ leads to no noticeable change in cumulative or average regret (see the below table). $R(t)$ denotes the cumulative regret up to round $t$, whereas $R(t)/t$ is the average regret at round $t$. We report $R(t)/t$ to check whether cumulative regret is sublinear.

2. Discussion of $\bar{p}$

We first clarify meaning of large $\bar{p}$. Recall that \bar p is defined as an upper bound on the non-click probability: $\bar{p} = \sup_{x}\sigma_0(x^{\top}\theta^\*).$ Consequently, a large $\bar{p}$ corresponds to a high–negative-feedback scenario.

Even though our regret bound may increase in the small-$K$ regime with particularly large $\bar{p}$, we emphasize that this is the first regret bound to explicitly capture and improve with increasing $K$, with the explicit dependence on both $K$ and $\bar{p}$. We believe this constitutes a significant and meaningful contribution to the community. This theoretical result is NOT just an artifact of the loose analysis. That is because we establish the same scale of lower bound (modulo the difference between $\bar{p}$ and $\underline{p}$), which further supports our theoretical findings and implications. That is, it may be possible in the worst-case scenario for the small-$K$ regime with particularly large $\bar{p}$, the regret may initially increase with $K$ but eventually decrease as $K$ becomes sufficiently large although such scenarios may not appear in practice. We sincerely believe that this finding should NOT be considered as weakness. It is rather the nature of the problem that our work presents for the first time as the true scaling.

Furthermore, we would like to highlight that in the larger bandit literature, it is common for different regret bounds to coexist, with each being tighter under different conditions. For example, in linear bandits, two widely recognized optimal regret bounds are: (1) $\tilde{\mathcal{O}}(d\sqrt{T})$, and (2) $\tilde{\mathcal{O}}(\sqrt{dT \log N})$, which additionally depends on the number of arms $N$. When the number of arms is relatively small (e.g., $N = \mathcal{O}(e^d)$), the bound $\tilde{\mathcal{O}}(\sqrt{dT \log N})$ is tighter. Conversely, when $N$ is large, $\tilde{\mathcal{O}}(d\sqrt{T})$ becomes the better guarantee.

Hence, it is not just a matter of which bound is tighter but rather what this work focuses is what is the true scale of the regret in cascading contextual bandit problem supported by both upper and lower bounds.

3. Additional Experiments with larger $K$

Following your suggestion, we run the MovieLens-$100K$ experiment with $K = 50$ and $K = 100$. As the Table 6 shows, cumulative regret remains sub-linear (indicated by the steadily falling the average regret $R(t)/t$). Crucially, the overall scale of the regret $R(t)$ diminishes as $K$ increases, exactly reflecting our theoretical claim that regret decreases once the cascade length is long.

4. Time–Complexity of DO-SWAP

Contrary to your concern, the DO-SWAP subroutine imposes neither significant computational overhead nor implementation difficulty. With a single partial sort that runs in $O(K)$ time, our agent selects the two most uncertain arms within the length-$K$ cascade $C_t$. Our MovieLens-100K experiment with K=5 (See the table below) supports this claim, showing that DO-SWAP consistently consumes only $\approx 0.7 \%$ of total cumulative runtime even as the round $t$ grows.

[Table Instruction]

• "Total": is the mean cumulative runtime of the full algorithm,
• "DO-SWAP": is the mean cumulative time spent in the DO-SWAP sub-routine,
• "Ratio": is the share of DO-SWAP within the total time. | $t$ | Total | DO-SWAP | Ratio | |-------|-------------|-------------|--------| | $1000$ | $1.825$ | $0.012$ | $0.7$% | | $2000$ | $3.446$ | $0.024$ | $0.7$% | | $3000$ | $4.910$ | $0.035$ | $0.7$% | | $4000$ | $6.309$ | $0.045$ | $0.7$% | | $5000$ | $7.687$ | $0.056$ | $0.7$% |

5. Applicability to Time-Varying Contextual Features

We would like to clarify that our current framework already supports time-varying contextual features. Section 3.2 (Problem Setting) explicitly models the environment using time-varying contextual features, confirming that our theoretical analysis already accommodates such dynamics.

Accordingly, the OMD + DO-SWAP algorithm is naturally applicable to dynamic environments where contextual features change over time. In our MovieLens-100K experiment, the agent observes time-varying features $x_{t,i}$ at every round $t$: a new user $u_t$ arrives, and the agent chooses among $1,642$ movies $i$. As reported in Section 7 (Numerical Study), UCB-CLB with DO-SWAP achieves sub-linear regret under this setting, showing in practice that the algorithm still performs well even as the contexts change over time.

6. Integrating OMD and DO-SWAP Introduces No Additional Challenges

OMD is used for parameter estimation, while DO-SWAP handles the cascading selection process. These two components operate independently of each other. For example, one could substitute OMD with an alternative estimator such as MLE, and DO-SWAP would remain fully functional without modification.

Thank you for taking the time to review our work. We sincerely appreciate your constructive feedback and provide our detailed responses below.

1. Discussion of Regularity Conditions

Could you kindly clarify what is meant by the "logistic noise parameters"? We assume this refers either to $\theta^\star$ or to the curvature parameter $\kappa$. Accordingly, we will address the boundedness of the three relevant quantities: the feature vector $x$, the true parameter $\theta^\star$, and the curvature parameter $\kappa$. Below, we explicitly show that these boundedness assumptions are made for convenience and can be easily relaxed or reformulated as definitions. Therefore, we believe they should not be viewed as weaknesses of our work.

1) Boundedness assumption on $x$ and $\theta^\star$ (Assumption 5.1): We would like to clarify that this assumption is made purely for convenience and cleaner presentation. If $x$ and $\theta^\star$ are bounded by a general constant $S$ (rather than 1), the regret bound simply scales with $\text{poly}(S)$. For example, if $\Vert x \Vert_{2} \le 1$ and $\Vert \theta^{\star} \Vert_2 \leq S$, the regret becomes $\tilde{\mathcal{O}} \left( S^{3/2} K \bar{p}^{K-1} d \sqrt{T} \right)$, since the confidence parameter scales as $\beta_{t,k}(\delta) = \tilde{\mathcal{O}}(S^{3/2} \sqrt{d})$.

2) Discussion about $\kappa$ (Assumption 5.3): We would like to highlight that $\kappa$ is always non-zero as long as the features and parameter vectors are bounded. In the logistic bandit literature, it is standard practice to define $\kappa$ explicitly—rather than assume it—based on problem parameters (e.g., Equation (2) of Faury et al., 2020 [1]). Therefore, we believe it is more appropriate to formally define $\kappa$ rather than assume its non-zeroness. For clarity, we will revise Assumption 5.3 to be a Definition in our final version.

[1] Faury, Louis, et al. "Improved optimistic algorithms for logistic bandits." International Conference on Machine Learning. PMLR, 2020.

2, Additional Experiments: KuaiRand Pure Click Datasets [2] As the current NeurIPS rebuttal guidelines prohibit the inclusion of figures, we instead present the results in the table below. $R(t)$ denotes the cumulative regret up to round $t$, whereas $R(t)/t$ is the average regret at round $t$. We report $R(t)/t$ to check whether cumulative regret is sublinear. Following the reviewer’s suggestion, we ran additional experiments with cascade lengths $K = 10$ on the KuaiRand-Pure dataset.

KuaiRand-Pure is a real-world recommendation benchmark derived from the short-video platform Kuaishou; it contains anonymised user–item interaction logs with click indicators, which we adopt as the binary reward signal for our bandit task. Consistent with our theoretical findings, the regret decreases as $K$ increases, confirming that our method scales favourably with longer cascades and remains robust across datasets.

(i) UCB-CLB with K=5

(ii) UCB-CLB with K=10

[2] Gao, Chongming, et al. "Kuairand: An unbiased sequential recommendation dataset with randomly exposed videos." Proceedings of the 31st ACM international conference on information & knowledge management. 2022.

3, Clarification on $\underline{p}$ vs $\bar{p}$

While our upper and lower bounds differ due to the gap between $\bar{p}$ and $\underline{p}$, these quantities are often overly conservative in practice. As a result, the realized regret typically lies between the two—significantly lower than the upper bound and higher than the lower bound—indicating that our algorithm is robust to the worst-case values of $\bar{p}$ and $\underline{p}$. To illustrate this, we provide a table below comparing the theoretical upper bound, theoretical lower bound, and the actual cumulative regret observed in an experiment with $\bar{p} = 0.8$ and $\underline{p} = 0.1$. In the table:

• "Upper Bound" refers to the theoretical regret upper bound,
• "Lower Bound" refers to the theoretical regret lower bound, and
• "Cum. Regret" refers to the cumulative regret actually incurred by our algorithm on the MovieLens 100K dataset.

Currently, we do not yet know how to close the gap between $\bar{p}$ and $\underline{p}$ to achieve minimax optimality. One promising direction is to pursue instance-dependent regret bounds, as in Abeille et al. (2021). For example, by defining $p^\star = \sigma_0((x^\star)^\top \theta^\star)$, where $x^\star$ is an optimal arm, one could derive $p^\star$-dependent regret bounds instead of relying on worst-case quantities like $\bar{p}$ and $\underline{p}$. While this is a meaningful direction, it falls outside the scope of the present work, and we leave it for future research. We thank the reviewer for this valuable and constructive suggestion. Moreover, note that our algorithm does not need to observe or know $\bar{p}$ or $\underline{p}$ at any point.

4. OMD vs. MLE Trade-offs in Low-noise Regimes

It remains unclear which method—OMD or MLE—is preferable. In a low-noise regime, click feedback is almost deterministic. Under the logistic model this means the parameter norm $S$ must be large (i.e., $\\| \theta\\|_2 \leq S$), reflecting a strong signal or a wide parameter space.

Recall that when $\\|\theta^\star\\|_2 \leq S$, our regret bound (that uses OMD) scales as $\tilde{\mathcal{O}}\left(S^{3/2} K \bar{p}^{K-1} d \sqrt{T} \right)$, which deteriorates as $S$ increases. In contrast, for MLE-based approaches, $S$-free regret bounds have been established in the GLM bandit literature (e.g., Lee et al., 2024 [3]). This suggests that a similar $S$-free regret might be achievable in our setting by adopting MLE and applying similar techniques. Alternatively, an adaptive warm-up strategy, as proposed by Lee and Oh [4], could also eliminate the dependence on $S$.

Because both MLE and carefully tuned OMD variants can avoid explicit $S$ dependence, deciding which approach is superior—even in low-noise scenarios—remains unresolved. Further work is required to pin down their precise statistical and computational trade-offs.

[3] Lee, Junghyun, Se-Young Yun, and Kwang-Sung Jun. "A Unified Confidence Sequence for Generalized Linear Models, with Applications to Bandits." Advances in Neural Information Processing Systems 37 (2024): 124640-124685.

[4] Lee, Joongkyu, and Min-hwan Oh. "Improved Online Confidence Bounds for Multinomial Logistic Bandits." Forty-second International Conference on Machine Learning.

5. Impact of Arm Pool Size $N$

Our regret bound—and the algorithm in practice—is $N$-independent; to substantiate this, we conduct additional experiments. Using the MovieLens-100K benchmark with cascade length $K=5$, we vary the arm pool from $N=2000, 2500, 3000$ movies while keeping the same optimal arm across all settings to ensure a fair comparison. The resulting cumulative-regret, $R(t)$ is reported in the table below.

Across all horizons the largest gap between any two $R(t)$ is $0.009$ (at $t=5000$), which is approximately $1\%$ of the regret scale in those rows. Thus, even when $N$ increases from $2000$ to $3000$, the regret remains almost unchanged, supporting our theoretical results that regret does not depend on $N$.

We appreciate your thoughtful feedback on our work. Below, we provide detailed responses to each comment and question.

1. Variance Lower-Bound Assumption

Before addressing the reviewer’s concern, we would first like to clarify the intended meaning of “variance” in the review. We assume the reviewer is referring to the parameter $\kappa$. In that case, we strongly believe that the existence of a non-zero $\kappa$ should NOT be viewed as a weakness of our paper, since $\kappa$ is always non-zero as long as the features and parameter vectors are bounded. In the logistic bandit literature, it is standard practice to define $\kappa$ explicitly—rather than assume it—based on problem parameters (e.g., Equation (2) of Faury et al., 2020 [1]). Therefore, we believe it is more appropriate to formally define $\kappa$ rather than assume its non-zeroness. For clarity, we will revise Assumption 5.3 to be a Definition in our final version.

To further elaborate on $\kappa$: this parameter captures the degree of non-linearity of the sigmoid function. Specifically, $\kappa$ becomes smaller when the agent selects actions across a wider range of the sigmoid. As such, $\kappa$ quantifies the difficulty of learning induced by the non-linearity of the logistic model. This dependence is not unique to our work—it has been unavoidable in much of the existing literature (Faury et al., 2020, 2021, 2022; Lee and Oh, 2024, 2025; Vial et al., 2022; Liu et al., 2024), whether it appears in the leading term or non-leading constants of the regret bounds.

In response to the reviewer’s question regarding the deterministic choice setting: such a setting corresponds to a degenerate case where each item is either (a) always clicked or (b) never clicked. Neither case is interesting from a learning or decision-making perspective. In case (a), the learner could simply select any $K$ items at random and incur zero regret, since every selected item leads to a click. In case (b), the learner also incurs zero regret, regardless of the selection, as the optimal reward is itself zero. Thus, the deterministic setting is uninformative and trivial in terms of both exploration and regret analysis.

[1] Faury, Louis, et al. "Improved optimistic algorithms for logistic bandits." International Conference on Machine Learning. PMLR, 2020.

2. Additional Experiments: larger $K$

In accordance with this year’s NeurIPS rebuttal guidelines, we are not permitted to include plots; thus, we present the results in tabular form below. $R(t)$ denotes the cumulative regret up to round $t$, whereas $R(t)/t$ is the average regret at round $t$. We report $R(t)/t$ to check whether cumulative regret is sublinear.

As per reviewer's request, we have conducted additional MovieLens benchmark experiments with larger $K = 50, 100$ to evaluate the robustness of our method. Consistent with our theoretical findings, the regret decreases as $K$ increases, demonstrating that our method scales favorably with the cascade length. The scale difference is enormous: for every round in the table, $R(t)$ at $K = 100$ is roughly $10^{15} \sim 10^{16}$ times smaller than at $K = 50$.

3. Large $\bar{p}$ Case

Even though our regret bound may increase in the small-$K$ regime with particularly large $\bar{p}$, we emphasize that this is the first regret bound to explicitly capture and improve with increasing $K$, with the explicit dependence on both $K$ and $\bar{p}$. We believe this constitutes a significant and meaningful contribution to the community. This theoretical result is NOT just an artifact of the loose analysis. That is because we establish the same scale of lower bound (modulo the difference between $\bar{p}$ and $\underline{p}$), which further supports our theoretical findings and implications. That is, it may be possible in the worst-case scenario for the small-$K$ regime with particularly large $\bar{p}$, the regret may initially increase with $K$ but eventually decrease as $K$ becomes sufficiently large although such scenarios may not appear in practice. We sincerely believe that this finding should NOT be considered as weakness. it is rather the nature of the problem that our work presents for the first time as the true scaling.

Furthermore, we would like to highlight that in the bandit literature, it is common for different regret bounds to coexist, with each being tighter under different conditions. For example, in linear bandits, two widely recognized optimal regret bounds are: (1) $\tilde{\mathcal{O}}(d\sqrt{T})$, and (2) $\tilde{\mathcal{O}}(\sqrt{dT \log N})$, which additionally depends on the number of arms $N$. When the number of arms is relatively small (e.g., $N = \mathcal{O}(e^d)$), the bound $\tilde{\mathcal{O}}(\sqrt{dT \log N})$ is tighter. Conversely, when $N$ is large, $\tilde{\mathcal{O}}(d\sqrt{T})$ becomes the better guarantee.

In the same spirit, our newly established bounds are optimal in the small-$\bar{p}$ regime, while for large $\bar{p}$, the existing bound of $\tilde{\mathcal{O}}(d\sqrt{T})$ remains optimal. We will incorporate this clarification into the final revision.

Additionally, we conduct an experiment to demonstrate the robustness of our algorithm to the value of $\bar{p}$ in practice. Importantly, the actual performance depends on the no-click probabilities $\sigma_0(x_{t,i}^\top \theta^\star)$ for items in the selected set $C_t$ (i.e., $i \in C_t$), rather than on the worst-case value $\bar{p} = \sup_x \sigma_0(x^\top \theta^\star)$ used in the regret analysis. As a result, the realized regret does NOT typically scale with $\bar{p}$—the worst-case analysis can be overly conservative.

The following table illustrates that **even when \bar{p** is large, the observed regret decreases monotonically as $K$ increases}, highlighting the practical stability of our method.

Thank you for your time to review our paper and for your valuable feedback. Here are our responses to each comment and question:

1. Gap between the Upper-Lower Bound Gap

As the reviewer pointed out, closing the gap between the current upper and lower bounds—i.e., matching $\bar{p}$ and $\underline{p}$—is indeed an important direction for future research. At present, we do not yet know how to achieve minimax optimality in this regime. One potential approach is to pursue instance-dependent regret bounds, as done by Abeille et al. (2021). For example, by defining $p^\star = \sigma_0((x^\star)^\top \theta^\star)$, where $x^\star$ is an optimal arm, one could try to derive $p^\star$-dependent regret bounds instead of relying on worst-case probabilities ($\bar{p}$ and $\underline{p}$). While promising, this line of work is beyond the current scope and we leave it for future work. We thank the reviewer for this valuable and constructive suggestion.

2. Discussion of Regret Bound for Small $K$ and Large $\bar{p}$

Even though our regret bound may increase in the small-$K$ regime with particularly large $\bar{p}$, we emphasize that this is the first regret bound to explicitly capture and improve with increasing $K$, with the explicit dependence on both $K$ and $\bar{p}$. We believe this constitutes a significant and meaningful contribution to the community. This theoretical result is NOT just an artifact of the loose analysis. That is because we establish the same scale of lower bound (modulo the difference between $\bar{p}$ and $\underline{p}$), which further supports our theoretical findings and implications. That is, it may be possible in the worst-case scenario for the small-$K$ regime with particularly large $\bar{p}$, the regret may initially increase with $K$ but eventually decrease as $K$ becomes sufficiently large although such scenarios may not appear in practice. We sincerely believe that this finding should NOT be considered as weakness. It is rather the nature of the problem that our work presents for the first time as the true scaling.

Furthermore, we would like to highlight that in the bandit literature, it is common for different regret bounds to coexist, with each being tighter under different conditions. For example, in linear bandits, two widely recognized optimal regret bounds are: (1) $\tilde{\mathcal{O}}(d\sqrt{T})$, and (2) $\tilde{\mathcal{O}}(\sqrt{dT \log N})$, which additionally depends on the number of arms $N$. When the number of arms is relatively small (e.g., $N = \mathcal{O}(e^d)$), the bound $\tilde{\mathcal{O}}(\sqrt{dT \log N})$ is tighter. Conversely, when $N$ is large, $\tilde{\mathcal{O}}(d\sqrt{T})$ becomes the better guarantee.

In the same spirit, our newly established bounds become much tighter than existing bounds for cascading contextual bandits, as $K$ increases, and optimal in the large-$K$ regime. We will incorporate this clarification into the final revision.

Additionally, we conduct an experiment to demonstrate the robustness of our algorithm to the value of $\bar{p}$ in practice. Importantly, the actual performance depends on the no-click probabilities $\sigma_0(x_{t,i}^\top \theta^\star)$ for items in the selected set $C_t$ (i.e., $i \in C_t$), rather than on the worst-case value $\bar{p} = \sup_x \sigma_0(x^\top \theta^\star)$ used in the regret analysis. As a result, the realized regret does NOT typically scale with $\bar{p}$—the worst-case analysis can be overly conservative.

The following table illustrates that even when $\bar{p}$ is large, the observed cumulative regret decreases monotonically as $K$ increases, highlighting the practical stability of our method.

3. Selection Rule for $i_t^{\scriptscriptstyle (1)}$ and $i_t^{\scriptscriptstyle (2)}$

Thank you for pointing out this omission. The exact rule for choosing the two swap arms is stated on page 7, line 226:

$

i_t^{\scriptscriptstyle (1)} = \arg\max_{i\in C_t} \dot\sigma_1 \bigl(x_{t,i}^{\top}\theta_t\bigr) \lVert x_{t,i}\rVert_{H_t^{-1}}, \quad i_t^{\scriptscriptstyle (2)} = \arg\max_{i\in C_t} \lVert x_{t,i}\rVert_{H_t^{-1}}.

$

To make this clear in the final version, we will (i) assign an explicit equation number to the formula above, and (ii) add a reference to the equation directly inside Algorithm 2 (page 5). We appreciate your careful reading and for helping us improve the clarity.

Step 6: Applying the triggering-probability equivalence technique

Next, the direct application of the triggering-probability equivalence (TPE) technique introduced by Liu et al. [3], which allows us to replace the summation over the cascade $C\_t$ weighted by the product of non-click probabilities with an equivalent expectation over the set of observed arms $O\_t$, yields the followings:

where the last eqaulity arises from applying the well-known elliptical potential lemma.

2. Lower Bound of Contextual Cascading Bandits

By the formulation of our instance in Appendix D.1, $\underline{p} := \inf\_x \sigma_0(x^\top \theta\_v) \le \frac{1}{2}$, hence $K \underline{p}^{K-1}\le 1, \quad\forall K\ge 1.$ It follows that the worst-case regret admits $\Omega \big(\min \lbrace K \underline{p}^{K-1}, 1\rbrace \cdot d\sqrt{T}\big)$. Together with our upper bound $\tilde{\mathcal O} \big(\min\lbrace K\bar{p}^{K-1},1\rbrace \cdot d\sqrt{T}\big)$, the bound matches up to the gap between $\underline{p}$ and $\bar{p}$.

[1] Lee, Junghyun, Se-Young Yun, and Kwang-Sung Jun. "A Unified Confidence Sequence for Generalized Linear Models, with Applications to Bandits." Advances in Neural Information Processing Systems 37 (2024): 124640-124685.

[2] Liu, Xutong, et al. "Batch-size independent regret bounds for combinatorial semi-bandits with probabilistically triggered arms or independent arms." Advances in Neural Information Processing Systems 35 (2022): 14904-14916.

[3] Liu, Xutong, et al. "Contextual combinatorial bandits with probabilistically triggered arms." International Conference on Machine Learning. PMLR, 2023.

We hope that these additional results help clarify the improvements in our regret bounds over prior works and address the reviewer’s concerns regarding the strength of our results. We would greatly appreciate it if these clarifications could be considered in your final assessment. Thank you again for your time and effort in serving as a reviewer.