- 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
-
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.
-
The paper establishes instance-dependent regret guarantees under batched feedback. In particular, matches the regret order of while requiring only logarithmically many batches in for fixed and .
Critical weaknesses
1. Unclear technical novelty and the role of the middle-position quota
Both and 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 -dependence in the regret guarantee
On homogeneous-gap instances, incurs an additional factor of compared with , yielding a regret bound proportional to , which can increase with . 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 batch-complexity guarantee:
Theorem 3 establishes a batch-count upper bound of . However, this guarantee can become uninformative when is large relative to , particularly in the many-armed regime . Could the authors clarify the parameter regimes in which this bound provides a meaningful improvement over the trivial bound ?
2. Significance of the batch-complexity lower bound in Theorem 4:
Theorem 4 derives its lower bound from the 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 ?
3. Effect of the list length on batch complexity: Theorem 3 does not capture a potential reduction in batch complexity as increases. Interestingly, Tables 2 and 4 suggest that increasing 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 on batch complexity would be helpful.
4. Regret–batch complexity tradeoff between BC-SAR and BC-UCB:
uses batches but incurs an additional factor in its regret bound, whereas matches the regret order of 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
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 . 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 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 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 , once , suboptimal item stops being selected, and the min-count rule limits its within-batch observations to , giving the rate without a quota or (Lemma 7, Theorem 2). In BC-SAR, rejection requires , 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 depend on the unknown and can be arbitrarily small, so Lemma 5 bounds how long stays active through the guaranteed first-position counts (Lemma 13). Keeping would bound 's loss by times its expected number of observations while active, but this number is not capped by 's own radius, and the bound we can obtain for it is again the recommendation count of Lemma 4. Lemma 3 therefore sets . 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 .
2: It is unclear how this relaxation limits the tightness of the static-grid guarantee.
When , as on the instances of our Theorem 4 (all attractions at most ), every position is examined with probability . Each weight in Theorem 5 then lies in , so setting it to loses at most a factor . The factor is instead the ratio 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, 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 , a route to removing 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 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 over a batch of length about , 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 (e.g., at , ; 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.
Response to Reviewer fwcz
We thank the reviewer for the precise questions, several of which led to new results in the revised PDF.
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, 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ρ,r. Whether a quota-free variant admits a guarantee is open.
In our proof, the extra K 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 K. Our new K sweep (Appendix B.8, Table 15) is consistent with this: relative to BC-UCB, BC-SAR does not grow proportionally to K, while the advantage of the quota-free variant grows with K (at μopt=0.1: 4663 vs. 4701 at K=2, but 1906 vs. 843 at K=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(logT) batches independent of L, whereas the batch count of BC-UCB is controlled through λ and grows with L; empirically, BC-SAR has lower regret below roughly 100 batches (Figure 4). Remark 4 and Section 6.4 now state this.
Let Rλ be the regret bound of Theorem 2 and Δmax:=μK−μL. If L≥2K and λ≥1, then M≤3ΔmaxRλ+1 (new Remark 3 and Appendix A.9). The batch bound is thus sublinear whenever the regret bound is, e.g., for fixed L,K and growing T; both become uninformative in the many-armed regime L≫T, as does the bound of CascadeUCB1.
We have extended it to every fixed K (General Response, Point 1), so the O(logT) batches of BC-UCB are within a loglogT factor of the necessary number at K=4,8 as in our experiments, not only at K=1. Two steps are specific to cascades: a round reveals up to K attractions, so crossing scales are measured in observations (T/L becomes KT/L); and K−1 anchor items, more attractive than all others, make every list with two or more non-anchor items incur Ω(1/K) regret, which reduces each round to the choice of one candidate. The result constrains only the number of batches, not the K factor of BC-SAR.
The decrease in Tables 2 and 4 is instance-dependent. In a new systematic sweep (L=64, T=200,000, K∈{2,4,8,16}, μopt∈{0.1,0.2,0.4}, 20 runs; Appendix B.8, Table 15), the batch count falls with K only when the cascade continues down the list: at μopt=0.1, observations per round grow from 1.9 to 8.2 and batches fall from 324 to 147; at μ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 μ, so a uniform guarantee such as Theorem 3 cannot capture this effect; consistently, the lower bound depends on K only through log(1+KT/L). Section 6.2 summarizes this.