acceptodds
Under review as a conference paper at ICLR 2027

Batched Cascading Bandits

Abstract

Cascading bandits model ordered recommendation under stochastic prefix feedback: in each round, a learner selects and orders out of items but observes outcomes only up to the first click. Standard cascading bandit algorithms update after every round, which can be impractical in real-world scenarios where instant feedback is not always available. We study batched cascading bandits, where the learner commits all recommendation lists in a batch using the feedback available at its start and updates the policy only at its batch endpoint. To address different batch constraints, we propose two algorithms: Batched Cascade Successive Accepts and Rejects (BC-SAR) and Batched Cascade Upper Confidence Bound (BC-UCB). Both algorithms combine first-position rotation with mechanisms tailored to their respective batch constraints. On homogeneous-gap instances with common attraction-probability gap and constant algorithm parameters, BC-SAR has expected regret using batches. BC-UCB has expected regret using batches. Numerical experiments evaluate our algorithms and examine their empirical performance under batched feedback.

Primary area:
learning theory
Keywords:
Multi-Armed Bandits, Cascading Bandits, Batched Bandits, Regret Analysis, Recommender Systems

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_fwczOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies batched cascading bandits, where feedback is available only at batch endpoints. The authors propose two algorithms, BC-SAR for static batching and BC-UCB for adaptive batching, and establish instance-dependent regret guarantees for both. In particular, BC-UCB achieves the same regret order as conventional CascadeUCB1 while reducing the number of policy updates. The paper also provides a batch-complexity lower bound and empirical evaluations of the proposed algorithms.

Critical strengths
  1. The paper studies batched cascading bandits, a relatively unexplored setting that combines cascading feedback with limited policy updates. Considering both static and adaptive batching makes the problem practically relevant.

  2. The paper establishes instance-dependent regret guarantees under batched feedback. In particular, BC-UCB\texttt{BC-UCB} matches the regret order of CascadeUCB1\texttt{CascadeUCB1} while requiring only logarithmically many batches in TT for fixed LL and KK.

Critical weaknesses

1. Unclear technical novelty and the role of the middle-position quota

Both BC-SAR\texttt{BC-SAR} and BC-UCB\texttt{BC-UCB} build on existing techniques from cascading and batched bandits, but their main technical novelty is not clearly distinguished from prior approaches. In particular, the theoretical necessity and contribution of the middle-position quota in BC-SAR deserve further clarification, especially since removing it improves empirical regret in the ablation experiments. A clearer discussion of the key technical insights and their differences from prior analyses would strengthen the paper.

2. Unclear KK-dependence in the BC-SAR\texttt{BC-SAR} regret guarantee

On homogeneous-gap instances, BC-SAR\texttt{BC-SAR} incurs an additional factor of KK compared with CascadeUCB1\texttt{CascadeUCB1}, yielding a regret bound proportional to K(L−K)K(L-K), which can increase with KK. Although the authors acknowledge this issue, it remains unclear whether the additional factor reflects an inherent difficulty of static batching or a limitation of the current analysis. This distinction is important for understanding the strength of the proposed regret guarantee.

Questions for authors

1. Practical relevance of the BC-UCB\texttt{BC-UCB} batch-complexity guarantee:

Theorem 3 establishes a batch-count upper bound of O(Llog⁡(1+KT/L))O(L\log(1+KT/L)). However, this guarantee can become uninformative when LL is large relative to TT, particularly in the many-armed regime L≫TL\gg T. Could the authors clarify the parameter regimes in which this bound provides a meaningful improvement over the trivial bound M≤TM\le T?

2. Significance of the batch-complexity lower bound in Theorem 4:

Theorem 4 derives its lower bound from the K=1K=1 subclass, where cascading bandits reduce to standard multi-armed bandits. Could the authors clarify how this result differs from existing lower bounds for batched multi-armed bandits and what additional insight it provides for cascading bandits with K>1K>1?

3. Effect of the list length KK on batch complexity: Theorem 3 does not capture a potential reduction in batch complexity as KK increases. Interestingly, Tables 2 and 4 suggest that increasing KK reduces the realized number of batches. Could the authors explain this discrepancy between the theoretical bound and empirical observations? A more systematic empirical investigation of the effect of KK on batch complexity would be helpful.

4. Regret–batch complexity tradeoff between BC-SAR and BC-UCB:

BC-SAR\texttt{BC-SAR} uses O(log⁡T)O(\log T) batches but incurs an additional KK factor in its regret bound, whereas BC-UCB\texttt{BC-UCB} matches the regret order of CascadeUCB1\texttt{CascadeUCB1} with a larger batch-count upper bound. Could the authors discuss whether this difference reflects a fundamental regret–batch complexity tradeoff or is primarily due to the different algorithmic designs and analyses?

8 comments
AuthorsOpenReview ↗

Response to Reviewer fwcz

We thank the reviewer for the precise questions, several of which led to new results in the revised PDF.

W1: The technical novelty and the role of the middle-position quota are unclear.

For the novelty, see General Response, Point 2 and our response to uDo3 (Q2). On the quota, we agree with the reviewer's reading: removing the quota lowers empirical regret (Table 7), and Section 6.4 now states this plainly. Its role is analytical. Lists are fixed within a batch of length about (a−1)tm−1(a-1)t_{m-1}, and without a cap an item with a stale high mean could occupy a middle position throughout; the quota gives a deterministic per-epoch recommendation bound (Lemma 4) at the price of the factor Cρ,rC_{\rho,r}. Whether a quota-free variant admits a guarantee is open.

W2 & Q4: It is unclear whether the extra KK in BC-SAR, and its gap to BC-UCB, is fundamental.

In our proof, the extra KK comes from the quota and the recommendation-based accounting (General Response, Point 3); it is not a proven property of static batching, and no lower bound separates static from adaptive grids in KK. Our new KK sweep (Appendix B.8, Table 15) is consistent with this: relative to BC-UCB, BC-SAR does not grow proportionally to KK, while the advantage of the quota-free variant grows with KK (at μopt=0.1\mu_{\mathrm{opt}}=0.1: 46634663 vs. 47014701 at K=2K=2, but 19061906 vs. 843843 at K=16K=16). The difference between the two algorithms therefore reflects design and analysis rather than a proven fundamental tradeoff. They also serve different constraints: BC-SAR runs on any prescribed static grid with O(log⁡T)O(\log T) batches independent of LL, whereas the batch count of BC-UCB is controlled through λ\lambda and grows with LL; empirically, BC-SAR has lower regret below roughly 100 batches (Figure 4). Remark 4 and Section 6.4 now state this.

Q1: When is the batch bound of Theorem 3 informative?

Let RλR_\lambda be the regret bound of Theorem 2 and Δmax⁡:=μK−μL\Delta_{\max}:=\mu_K-\mu_L. If L≥2KL\ge2K and λ≥1\lambda\ge1, then M≤3 Δmax⁡Rλ+1M\le3\,\Delta_{\max}R_\lambda+1 (new Remark 3 and Appendix A.9). The batch bound is thus sublinear whenever the regret bound is, e.g., for fixed L,KL,K and growing TT; both become uninformative in the many-armed regime L≫TL\gg T, as does the bound of CascadeUCB1.

Q2: What does Theorem 4 add beyond batched-MAB lower bounds for K>1K>1?

We have extended it to every fixed KK (General Response, Point 1), so the O(log⁡T)O(\log T) batches of BC-UCB are within a log⁡log⁡T\log\log T factor of the necessary number at K=4,8K=4,8 as in our experiments, not only at K=1K=1. Two steps are specific to cascades: a round reveals up to KK attractions, so crossing scales are measured in observations (T/LT/L becomes KT/LKT/L); and K−1K-1 anchor items, more attractive than all others, make every list with two or more non-anchor items incur Ω(1/K)\Omega(1/K) regret, which reduces each round to the choice of one candidate. The result constrains only the number of batches, not the KK factor of BC-SAR.

Q3: Why does the batch count fall with KK in experiments but not in Theorem 3?

The decrease in Tables 2 and 4 is instance-dependent. In a new systematic sweep (L=64L=64, T=200,000T=200{,}000, K∈{2,4,8,16}K\in\{2,4,8,16\}, μopt∈{0.1,0.2,0.4}\mu_{\mathrm{opt}}\in\{0.1,0.2,0.4\}, 20 runs; Appendix B.8, Table 15), the batch count falls with KK only when the cascade continues down the list: at μopt=0.1\mu_{\mathrm{opt}}=0.1, observations per round grow from 1.9 to 8.2 and batches fall from 324 to 147; at μopt=0.4\mu_{\mathrm{opt}}=0.4, observations saturate near 2.6 and batches do not fall (339–432). Only the first position is observed with probability bounded away from zero for every μ\mu, so a uniform guarantee such as Theorem 3 cannot capture this effect; consistently, the lower bound depends on KK only through log⁡(1+KT/L)\log(1+KT/L). Section 6.2 summarizes this.

Given the substantial changes in the revised manuscript and the limited time available, I focused my review on BC-SAR. My comments below concern this algorithm and its analysis.

My main concern is how effectively BC-SAR addresses the interaction between batched feedback and cascade feedback. The difficulty of batch setting is that the learner can not change their decision round by round, while the difficulty of cascade setting is that the observation is not guaranteed and depends on the order. In cascading bandits, placing an item later in the list is not solely a disadvantage: although it reduces opportunities to observe the item(in terms of information acquisition), its contribution to the regret upper bound is also scaled down by its observation probability (in terms of regret accounting). A useful feature of the cascade regret decomposition is that an item's contribution to the regret upper bound is weighted by its observation probability. This couples the difficulty of obtaining observations with the loss charged to that item.

The BC-SAR analysis discards this coupling by Pr⁡(i observes)≤1\Pr(i \text{ observes}) \le 1. The analysis counts a potential loss whenever an item is recommended, but relies on first-position observations to guarantee learning progress. Rotation ensures that every active item receives these observations, while the quota prevents it from being recommended too often in middle positions relative to how often it is placed first. Together, these mechanisms keep the loss counted in the analysis from becoming too large relative to the guaranteed observations. Thus, I also consider this use of the cascade structure to control regret a contribution in its own right.

However, I also view this as a methodological trade-off: the analysis obtains a tractable route to handling batch constraints by treating the cascade feedback structure conservatively. Rotation addresses observation starvation, but the regret analysis does not preserve the favorable relationship between observation probability and regret. The quota then limits the cost of this relaxation. Consequently, these mechanisms appear to enable a recommendation-count-based elimination analysis while controlling the loss introduced by that reduction.

This leaves me unconvinced that the static-grid result sufficiently resolves the interaction between the two feedback constraints. BC-SAR provides a valid regret guarantee (I checked the key steps of the proof and did not identify errors), but its analysis sacrifices an important feature of cascading bandits to accommodate batch-wise elimination. The additional KK factor makes the cost of this choice explicit. The reported improvement when removing the quota further raises the question of how strongly the algorithmic design is driven by the requirements of the proof.

Author's response clarifies why existing sequential and batched methods cannot be applied directly, and why first-position rotation is useful. My remaining concern is the trade-off made in BC-SAR's analysis: it handles batch constraints through recommendation-based regret accounting, while giving up the favorable relationship between observation probability and regret. I would appreciate a clearer discussion of why this approach was chosen and how the resulting loss of tightness limits the static-grid guarantee. This would help distinguish the contribution of the proposed mechanisms from the limitations of the analysis they support.

We thank the reviewer for checking the proof of BC-SAR and for this question on the trade-off in its analysis.

1: BC-SAR bounds the observation weight by 11 instead of preserving the coupling between observations and regret.

Observation weighting closes the bound when an item's own observations cap its future selection, as in BC-UCB: on E\mathcal E, once Nim>2β/Δi2N_i^m>2\beta/\Delta_i^2, suboptimal item ii stops being selected, and the min-count rule limits its within-batch observations to λNim+1\lambda N_i^m+1, giving the (L−K)(L-K) rate without a quota or KK (Lemma 7, Theorem 2). In BC-SAR, rejection requires Ui<θrU_i<\theta_r, which also depends on the counts of the other active items, and eliminations take effect only at the endpoints of the static grid. Middle-position examination rates ∏ℓ<k(1−μAt(ℓ))\prod_{\ell<k}(1-\mu_{A_t(\ell)}) depend on the unknown μ\mu and can be arbitrarily small, so Lemma 5 bounds how long ii stays active through the guaranteed first-position counts Nj(tm−1)≥1+⌊tm−1/L⌋N_j(t_{m-1})\ge1+\lfloor t_{m-1}/L\rfloor (Lemma 13). Keeping Pt(Gi,σt(i),t)\mathbb P_t(G_{i,\sigma_t(i),t}) would bound ii's loss by Δi\Delta_i times its expected number of observations while active, but this number is not capped by ii's own radius, and the bound we can obtain for it is again the recommendation count of Lemma 4. Lemma 3 therefore sets Pt(Gi,σt(i),t)≤1\mathbb P_t(G_{i,\sigma_t(i),t})\le1. The weight would give a smaller bound only on instances where deep positions are rarely examined, and that bound would depend on the examination probabilities of lists planned at tm−1t_{m-1}.

2: It is unclear how this relaxation limits the tightness of the static-grid guarantee.

When μ1≤1/K\mu_1\le1/K, as on the instances of our Theorem 4 (all attractions at most 1/(2K)1/(2K)), every position k≤Kk\le K is examined with probability ∏ℓ<k(1−μAt(ℓ))≥(1−1/K)K−1≥1/e\prod_{\ell<k}(1-\mu_{A_t(\ell)})\ge(1-1/K)^{K-1}\ge1/e. Each weight in Theorem 5 then lies in [1/e,1][1/e,1], so setting it to 11 loses at most a factor ee. The factor KK is instead the ratio Cρ,r=1+ρ(r−1)=O(K)C_{\rho,r}=1+\rho(r-1)=O(K) between the recommendations allowed per first-position placement (Lemma 4) and the first-position observations that bound stopping durations (Lemmas 5, 6 and 13). Thus, even if regret were charged to observations rather than recommendations, KK would remain on these instances as long as Lemma 5 counts only first-position observations. Since middle positions are then also examined with probability at least 1/e1/e, a route to removing KK is to credit middle-position observations of competing items in Lemma 5. This needs a lower bound on their middle-position exposure, which the greedy rule with frozen means does not provide, so whether KK can be removed on static grids remains open.

3: The quota ablation raises the question of how to separate the proposed mechanisms from the requirements of the proof.

Relative to the full method, the middle-position quota is the only component whose removal lowers regret. Removing acceptance or rejection raises regret on both ablation profiles (Table 7), placing accepted items first raises it on all three profiles (Table 14), and replacing first-position rotation with a uniformly random first item raises it on the single-strong profile without a significant reduction on the low-attraction profile (Table 7). The quota is needed by the analysis: BC-SAR fills middle positions greedily from frozen batch-start means μ^i(tm−1)\widehat\mu_i(t_{m-1}) over a batch of length about (a−1)tm−1(a-1)t_{m-1}, and the quota prevents a suboptimal item with a stale high mean from occupying a middle position throughout the batch (Lemma 4). The same cap also binds on high-mean optimal items that are not yet accepted, a likely reason why removing it lowers regret (Table 7), especially at larger KK (e.g., 1906→8431906\to843 at μopt=0.1\mu_{\mathrm{opt}}=0.1, K=16K=16; Table 15, Appendix B.8). A cap that keeps a static-grid guarantee without restricting such items as early is a natural direction. We will add this discussion to Remark 4 in the final version.

Reviewer_uDo3OpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

Cascading bandits is a well-known bandit model where in each round (total of T rounds), the user is shown a list of ordered items (K out of L total items; typically K << L). The user views sequentially until the first positive item (thus feedback is of the form ‘0001xxxx’, where 0 is not preferred, 1 is preferred, and x is unseen). This paper studies a couple of batched variants (static feedback times vs adaptive feedback times) where the feedback is available at M time instances with M < T, and batched feedback (instead of per-round feedback) at times: 0 < t_0 < t_1 … t_M <= T (in the theorems, M = O(log T) ).

The algorithms the authors develop are elimination-style with accept/reject for selecting list to display, and order based on a couple of different criteria (first is least first-position; next set based on estimated reward prob). They show upper bounds on regret for this setting (the multiplier to the (L-K) term in the standard cascading bandit problem).

Critical strengths

The problem is cleanly formulated. This seems like a natural extension to the standard cascading bandit. In terms of the algorithm, the authors use an elimination-style for list membership selection but the ordering is designed for this specific problem setting. The resulting bounds are clear.

Critical weaknesses

First, there are no matching lower bounds (Theorem 4, in my opinion, is a somewhat narrow special case). Indeed for the cascading bandit problems, there are papers with general lower bounds for the general K, L setting. I would have hoped that for the batched setting as well, the paper would show such results. Second, it is not clear to me what the new elements in the proofs are. While they are involved (I only skimmed through them in the appendix so I might have missed subtleties), they mostly seem standard arguments. Finally, while the batching setting at a high-level is reasonable, are there are concrete real settings where this is compelling?

Questions for authors

The questions I have for the authors correspond to the three weaknesses above, namely, is it possible to have a more general lower bound, can you highlight the innovations in the proof, and can you provide a compelling real-world setting. I am happy to reevaluate my score based on the response.

2 comments
AuthorsOpenReview ↗

Response to Reviewer uDo3

We thank the reviewer for the positive assessment and for the openness to re-evaluate.

W1/Q1: Theorem 4 is a narrow special case; a general lower bound is missing.

Following this comment, we have extended Theorem 4 from K=1K=1 to every fixed list length: logarithmic regret requires Ω(log⁡(1+KT/L)/log⁡log⁡T)\Omega(\log(1+KT/L)/\log\log T) batches, static grids included. Combined with the lower bound of Kveton et al. (2015), which applies to all batched policies and which BC-UCB matches up to a constant factor (new Remark 2), BC-UCB is near-optimal in both regret and the number of batches for every fixed KK and LL (General Response, Point 1). The extension measures crossing scales in observations and adds K−1K-1 anchor items, so that each round reduces to choosing one candidate.

W2/Q2: The new elements in the proofs are unclear.

Confidence events, elimination and UCB comparisons are standard. What fails under cascade censoring is the assumption of standard batched arguments that planned plays yield samples: a planned position may be rarely examined. Our proofs replace it in three places.

  • Batch count of BC-UCB (Lemma 8, Theorem 3). Rarely-switching analyses (UCB2; Abbasi-Yadkori et al., 2011) rely on a count doubling before each update, but the smallest selected count need not grow during a batch. With first-position rotation, ∑ilog⁡Ni\sum_i\log N_i grows by at least λ/(4λ+6)\lambda/(4\lambda+6) in every batch, whatever the clicks.
  • Regret of BC-UCB (Lemma 7, Theorem 2). The min-count rule bounds within-batch observations by λNim+1\lambda N_i^m+1 for every selected item, so stale radii telescope and batching costs only a constant CλC_\lambda, with no factor KK.
  • BC-SAR on static grids (Lemmas 3–6, 13, 14). Batched elimination allocates samples in advance; a cascade list guarantees observations only at the first position. Lemma 13 gives a pathwise first-position balance, the quota bounds recommendations (Lemma 4), and acceptance stops the adjacent-gap terms of heterogeneous optimal items (Lemmas 3, 5, 6).

W3/Q3: A concrete real-world setting is missing.

Deezer's playlist carousel (Bendada, Salha and Bontempelli, RecSys 2020, cited in our paper) combines cascade-based updates with feedback processed in daily batches and was evaluated in an online A/B test. In our notation, one list interaction is a round and one update window is a batch. Their model is richer (contexts, a different examination model); ours isolates the interaction between censoring and batching. More generally, production rankers refresh on fixed schedules (static grid) or decide when to retrain (adaptive grid, where BC-UCB's rule acts as a data-driven retraining trigger); Section 1 now describes both.

Thank you for the response. I will consider this carefully during the discussions.

Reviewer_HTJYOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

The paper introduces two bandit algorithms dedicated to batched flavor of the cascading setting. One algorithm (BC-SAR) assume the batches defined before hand and is based on successive reject ideas, the other (BC-UCB) chooses its batches online.

An instance-dependant upper-bound of the regret is proved for both algorithms, and some experiments show their behavior in practice.

Critical strengths

new setting with (maybe) new challenges Applying batched approaches to combinatorial setting is non-trivial as the arm to be played is a combination of elements, which explodes the set of potential strategy to balance exploration and exploitation.

However, studies on cascading bandits have shown that despite its combinatorial aspect, the true nature of this setting is extremely close to standard independent bandit: distinguish the KK-th element from the L−KL-K sub-optimal ones. This shines in the regret bound of SotA algorithms which scales in (L−K)(L-K). Some "recent" papers stress more this aspect :

  • Tor Lattimore, Branislav Kveton, Shuai Li, Csaba Szepesvá. TopRank: A practical algorithm for online stochastic ranking. NeurIPS'18
  • Chang Li, Branislav Kveton, Tor Lattimore, Ilya Markov, Maarten de Rijke, Csaba Szepesvári, Masrour Zoghi. BubbleRank: Safe Online Learning to Re-Rank via Implicit Click Feedback. UAI'20
  • Camille-Sovanneary Gauthier, Romaric Gaudel, Elisa Fromont. UniRank: Unimodal Bandit Algorithms for Online Ranking. ICML'22
Critical weaknesses

To large regret when batches are fixed The upper-regret bound of BC-SAR scales K(L−K)K(L-K) while it should be possible to design an algorithm with regret bound scaling in C(L−K)C(L-K) where CC only depend on the layout of the batches. Either BC-SAR has to be changed, or its analysis is not tight enough.

Many imprecisions/incorectness in the writting

  • From Line 116 to 126, the generation process of wtw_t is not expressed. Therefore the expected reward of SS cannot be derived.
  • L130: To define the UNIQUE S∗S^*, you have to prove or assume its uniqueness
  • choose between notations qiq_i and QiQ_i
  • while frequently used in bandit papers, [L] is not an international standard notation. Please define it somewhere.
  • L 151: it is claimed that ties are broken based on item index. It's unclear on which index.
  • It's unclear which guarantees BC-SAR has regarding the size of P\cal P
  • It's unclear which are the properties of sets A\cal A, P\cal P, and R\cal R
Questions for authors

Questions

  • On which index are broken the ties? Is it on a random index, or on the index presented the line before (which corresponds to the right order on the elements)?
  • What are the guarantees for BC-SAR regarding the size of P\cal P? Is it always smaller than KK or than K−1K-1?
  • Is there a more intuitive definition of sets A\cal A, P\cal P, and R\cal R. Typically a mathematical definition without recursion, or at least a set of properties of these sets.

Remarks

  • For the algorithms to be used in practice, it's better if they do not assume the knowledge of TT (currently it is required to define rad(n)rad(n)).
  • I'm pretty sure we can design an algorithm which puts the active elements AFTER the accepted ones. Indeed, either any of the active element as an acceptation probability of 1, and we do not care about the rest of the element, or all of the active elements have a probability smaller than 1, and they are guaranted to be tested regularly. The interest of such alternative design of the recommendation is that it puts first the most promising elements, which is more appealing for the users.
2 comments
AuthorsOpenReview ↗

Response to Reviewer HTJY

We thank the reviewer for the detailed reading.

S1: Cascading bandits are close to independent bandits.

We agree that for sequential cascading bandits regret is governed by separating the KK-th item from the L−KL-K others (Kveton et al., 2015), and UniRank attains this under the cascade model. This closeness relies on per-round adaptivity, which batching removes: a batch plan fixes positions, not observations (General Response, Point 2). Consequently, count-based schedules stall without rotation (3017 vs. 280 batches, Table 9), batch plans can rely only on first-position observations (Lemmas 8 and 13), and batched versions of sequential cascading algorithms are worse than ours in all eight configurations. Section 2 now discusses TopRank, BubbleRank and UniRank and contrasts their per-round updates with the batch constraint.

W1: BC-SAR's K(L−K)K(L-K) regret on static grids is not tight.

Static grids are where batching and censoring interact most strongly: an epoch is fixed in advance and only first-position observations are guaranteed, so batched elimination (Gao et al., 2019), which allocates samples in advance, does not transfer. We are not aware of a static-grid algorithm for batched cascading bandits with an instance-dependent guarantee of this form, and we do not claim the KK factor is necessary; a C(L−K)C(L-K) bound would be welcome. On adaptive grids, BC-UCB attains the (L−K)(L-K) rate (Theorem 2). General Response, Point 3 explains where the factor enters our analysis.

W2: The problem setup and notation are imprecise.

Each listed point concerns presentation, and none identifies an incorrect step or statement. All are fixed in the revised PDF.

  • (a) Generative model (L116–126): wt∼⨂i=1LBernoulli(μi)w_t\sim\bigotimes_{i=1}^L\mathrm{Bernoulli}(\mu_i), independent across rounds, now stated before f(S)f(S) (Section 3.1).
  • (b) Uniqueness of S⋆S^\star (L130): follows from μK>μK+1\mu_K>\mu_{K+1}, now stated before the first use of S⋆S^\star.
  • (c) [L][L]: [L]:={1,…,L}[L]:=\{1,\dots,L\} is defined at first use.
  • (d) qiq_i vs. QiQ_i: both are intended. QiQ_i is persistent and chooses the first position; qi,diq_i,d_i are epoch-local and used only by the quota (Section 4; new table of counters in Appendix A.1).
  • (e) Tie-breaking and P,A,R\mathcal P,\mathcal A,\mathcal R: see Q1–Q3 below.

Q1: Which index is used for tie-breaking: a random one, or the μ\mu-sorted one?

A fixed item label chosen independently of μ\mu (equivalently, a random label), not the μ\mu-sorted index. The indexing by decreasing μ\mu is notation for the analysis only, and the algorithms never use it (Section 3.2). All results hold for any tie-breaking rule: the selection steps enter the proofs only through non-strict inequalities, and acceptance and rejection require strict confidence separation. In the experiments, items are randomly permuted in every run (Appendix B.1).

Q2: Is ∣P∣|\mathcal P| at most KK or at most K−1K-1?

At most KK, and ∣P∣=K|\mathcal P|=K can occur: when exactly r:=K−∣P∣r:=K-|\mathcal P| active items remain, all of them are accepted, and from then on every list is ord(P)\mathrm{ord}(\mathcal P) (new Proposition A.2).

Q3: What are the properties of P,A,R\mathcal P,\mathcal A,\mathcal R, and is there a non-recursive definition?

Yes. Let r:=K−∣P∣r:=K-|\mathcal P|, and say that jj is confidently better than ii if Lj>UiL_j>U_i. At each endpoint, reject every active item for which at least rr active items are confidently better; then accept the largest group of the first k<rk<r remaining active items in decreasing μ^\widehat\mu that are each confidently better than every other active item (or all of them if exactly rr remain). One pass reaches the fixed point of the submitted loop (new Lemma A.1), so the outputs are unchanged. Proposition A.2 shows that the three sets partition [L][L]; P\mathcal P and R\mathcal R only grow; ∣P∣≤K|\mathcal P|\le K; on the confidence event (P≥1−1/T\mathbb P\ge1-1/T), P⊆S⋆\mathcal P\subseteq S^\star and R∩S⋆=∅\mathcal R\cap S^\star=\varnothing.

Remark 1: The algorithms require knowing TT.

Both algorithms have anytime versions with bounds of the same order (for BC-SAR, when K≤L/2K\le L/2; new Appendix A.8): BC-UCB only changes its confidence level, and BC-SAR uses exponential doubling (Besson and Kaufmann, 2018), which keeps a static grid with O(log⁡T)O(\log T) batches.

Remark 2: Accepted items could be placed before active ones.

Under the cascade model, the click probability depends only on the set, so this reordering does not change the per-round reward; it only thins the observations of active items by ∏j∈P(1−μj)\prod_{j\in\mathcal P}(1-\mu_j) and removes the pathwise guarantee of Lemma 13. UniRank (Remark 5.2) makes the same point about exploring at the top under the cascade model. In a new ablation (Appendix B.7, Table 14), the reordered variant has higher regret on all three profiles tested (e.g., 519→939519\to939 on single-strong).

Thank you again for your detailed review. We would like to share a brief summary of the revisions and clarifications we made in response to your comments. Section 3.1 of the revised manuscript specifies the product Bernoulli model for wtw_t and the strict gap ensuring a unique top-KK set. Section 3.2 clarifies tie-breaking, and Section 4 distinguishes the roles of QiQ_i and qiq_i in BC-SAR. Lemma A.1 proves that one pass of SAR-Update returns the same sets as the original loop, and Proposition A.2 establishes the structural properties of the accepted, active, and rejected sets as well as their correctness on the confidence event. We hope these pointers are helpful when reviewing the revised manuscript.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General Response to all reviewers

We thank the reviewers for their careful reading. We have uploaded a revised PDF of our paper with all changes in blue. New in the revision are Remarks 2–3, Lemma A.1, Proposition A.2, a counter table in Appendix A.1, and Appendices A.8–A.9 and B.7–B.8 (Tables 14–15); all other numbers of the submission are unchanged, except that the former Remark 2 is now Remark 4.

Point 1 (uDo3 W1/Q1; fwcz Q2): The batch lower bound covers only K=1K=1.

Theorem 4 now holds for every fixed KK, and BC-UCB is near-optimal in both regret and batches. The revised Theorem 4 shows that, for each fixed KK, logarithmic regret requires Ω(log⁡(1+KT/L)/log⁡log⁡T)\Omega(\log(1+KT/L)/\log\log T) batches, static grids included (Appendix A.6). On the regret side, every batched policy is a sequential policy, so the lower bound of Kveton et al. (2015) applies, and BC-UCB matches it in L−KL-K, Δ\Delta and log⁡T\log T up to a constant factor for fixed pp, KK and λ\lambda when log⁡L=O(log⁡T)\log L=O(\log T) (new Remark 2). Hence BC-UCB attains the optimal regret order with a number of batches within a log⁡log⁡T\log\log T factor of the necessary one, for every fixed KK and not only K=1K=1.

Point 2 (HTJY S1; uDo3 W2/Q2; fwcz W1): It is unclear what is new beyond independent and standard batched bandits.

Batching delays every update, which invalidates both the analyses of sequential cascading algorithms and the usual batched remedies. Sequential cascading algorithms (CascadeUCB1, CascadeKL-UCB, CTS, TS-Cascade) bound regret by showing that a suboptimal item stops being recommended once it has about log⁡T/Δ2\log T/\Delta^2 observations (Kveton et al., 2015); this needs indices refreshed every round. In a batch the list is fixed, so an item chosen from stale indices keeps its position for the rest of the batch, about (a−1)tm−1(a-1)t_{m-1} rounds on a geometric grid, and generic delayed-feedback reductions (Joulani et al., 2013) add a term that grows with this delay, a constant fraction of TT. With batch-deferred updates, all four have higher regret than ours in all eight synthetic configurations (Section 6.1, Appendix B.6). Batched multi-armed bandit methods handle the delay by fixing in advance how many samples each arm receives (Gao et al., 2019), or by ending a batch when a count doubles (UCB2; Abbasi-Yadkori et al., 2011). Both assume that planned plays yield samples, which fails in a cascade: a plan fixes only positions, and an item at position kk is observed at rate ∏j<k(1−μA(j))\prod_{j<k}(1-\mu_{A(j)}), which is unknown and can be arbitrarily small. The learner can plan exposure but not information. Without first-position rotation, count-based batching stalls (3017 instead of 280 batches, Table 9). We restore the arguments through first-position rotation and the min-count rule of BC-UCB (Lemmas 7–8) and through recommendation-based accounting in BC-SAR (Point 3).

Point 3 (HTJY W1; fwcz W2, Q4): The extra KK factor in BC-SAR's regret may be an artifact of the analysis.

Static grids are the hardest case of Point 2, and the extra KK reflects how our analysis handles it; we do not claim it is necessary. A sequential learner can react after every round when deeper positions go unobserved, whereas a static plan fixes an entire epoch in advance, and only its first-position observations are guaranteed. Batched elimination (Gao et al., 2019), which allocates samples in advance, does not transfer, and we are not aware of earlier static-grid algorithms for batched cascading bandits with instance-dependent guarantees. Our analysis therefore charges regret to recommendations rather than observations (Lemma 3) and bounds recommendations per epoch through the middle-position quota, at a factor 1+ρ(r−1)=O(K)1+\rho(r-1)=O(K) (Lemma 4); these two steps are where KK enters. No lower bound attributes this factor to static batching, and we state its necessity as an open question (Remark 4). In a new sweep over K∈{2,4,8,16}K\in\{2,4,8,16\} (Appendix B.8), the regret of BC-SAR stays within 2.1–6.2 times that of BC-UCB, without growth proportional to KK.

Point 4 (HTJY W2): The writing has many imprecisions.

All points are fixed, and none affects any statement or proof. They concern the generative model, the uniqueness of S⋆S^\star, [L][L], qi/Qiq_i/Q_i, the tie-breaking label and P,A,R\mathcal P,\mathcal A,\mathcal R (our response to HTJY, W2 and Q1–Q3). SAR-Update now performs one rejection and one acceptance step with a direct definition of the three sets (new Lemma A.1 and Proposition A.2); it returns the same sets as before, so all results and experiments are unchanged.

Other revisions: concrete deployment settings (Section 1; uDo3 W3/Q3); anytime versions of both algorithms (Appendix A.8; HTJY Remark 1); an AcceptedFirst ablation (Appendix B.7; HTJY Remark 2); the regime in which the batch bound is informative (Remark 3; fwcz Q1); the quota-free ablation stated plainly (Section 6.4; fwcz W1); TopRank, BubbleRank, UniRank and low-switching methods in Section 2 (HTJY S1).

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.