PaperlayerView exact revision on arXiv

Source-linked AI summary

Cascading Bandits with Noisy Observations: Algorithms and Regret Bounds

Yashaswini Kaluguri, Nikhil Karamchandani

arXiv:2610.29381v1cs.LGstat.ML

TL;DR

Noisy, costly observations complicate choosing and ordering arms in cascading bandits. The paper classifies when per-arm scores characterize those decisions and develops UCB algorithms, including DP-UCB for general cases. It establishes regret guarantees for both regimes, including matching lower bounds for the score-based algorithm.

  • Problem

    The central question is how noisy, costly observations affect optimal shortlist selection and ordering, which otherwise requires combinatorial search over both choices.

    Source: §I · p. 1, §III · p. 3

  • Method

    The paper classifies noise regimes by whether per-arm scores characterize selection and ordering, then develops UCB algorithms for score-based and general cases, including DP-UCB.

    Source: A. Our Contributions · p. 2

  • Results

    Θ((L−K) log T) regret is achieved by the score-based algorithm with matching lower bounds, while DP-UCB has O(LK log T) instance-dependent regret.

    Source: A. Our Contributions · p. 2

  • Takeaways & Limitations

    Experiments on synthetic and real-world settings show that the proposed algorithms substantially outperform other baselines.

    Source: §VII · p. 8

Abstract

from arXiv · show

We propose a novel stochastic cascading bandit setup where probing an ordered shortlist of $K$ out of $L$ arms incurs position-dependent costs, and the learner observes only noisy feedback regarding each arm's true output. We identify a sub-class of noise models for which the optimal shortlist can be found by sorting arms according to a per-arm score: such a score exists for both selection and ordering when the channel has no false positives, and for ordering alone (but not selection) when measurements are costless; however in general neither selection nor ordering is separable once noise and cost are both present. For the case where both selection and ordering scores exist, we provide a UCB-based algorithm with $O((L-K)\log T)$ instance-dependent regret over a time horizon $T$, which matches an algorithm-agnostic lower bound (up to constant factors). For the more challenging scenario where scores don't exist, we develop a new algorithmic template, DP-UCB, that embeds optimism directly inside an exact dynamic program, yielding $O\big(LK\log T\big)$ regret. Finally, we validate our theoretical results through extensive numerical evaluations and simulations over both synthetic and real-world datasets.

I. INTRODUCTION · A. Our Contributions · II. PROBLEM FORMULATION

The paper studies cascading bandits with costly, noisy observations, classifies when shortlist decisions admit per-arm scores, and develops algorithms with regret guarantees. It formalizes the cascade, feedback, and regret used to evaluate those algorithms.

I. INTRODUCTION

  • Cascading bandits model ranked-list interactions: users inspect items sequentially and select the first attractive one, leaving items after the selection unobserved.The paper focuses on noisy feedback, which can affect both shortlist inclusion and ordering, especially when observations are costly.Source: §I · p. 1

A. Our Contributions

  • The paper partitions noise models into score-based regimes, where ranking arms by explicit scores yields an optimal shortlist, and a general regime without that characterization.The score-based regimes are Case 1 and Shared-Channel; the general regime is Case 2.Source: A. Our Contributions · p. 2
  • TOP-K-P(Y = 1)-UCB exploits ranking scores but requires prior knowledge of score-based assumptions, whereas structure-agnostic DP-UCB uses dynamic programming and needs no noise-regime knowledge.DP-UCB embeds the combinatorial shortlist optimization in dynamic programming.Source: A. Our Contributions · p. 2
  • TOP-K-P(Y = 1)-UCB achieves optimal regret scaling Θ((L−K) log T), with matching lower bounds up to constants; DP-UCB has an O(LK log T) bound that becomes O(1) when K = L.The TOP-K guarantee applies in Case 1 and shared-channel regimes; the DP-UCB bound holds irrespective of noise regime.Source: A. Our Contributions · p. 2
  • Experiments on synthetic instances, MovieLens-1M, and an LLM cascade built from news headlines report significantly better regret for the proposed algorithms than various benchmarks.The LLM cascade uses LLM-as-a-judge evaluators.Source: A. Our Contributions · p. 2

II. PROBLEM FORMULATION

  • At each round, the learner chooses an ordered shortlist of K distinct arms from L; each arm has an independent Bernoulli success state and an arm-specific noisy binary observation channel.The channel is defined by false-positive and false-negative rates. A positive observation halts the cascade and triggers a probe whose position-m cost is mτ; a successful probe yields net reward 1 − mτ.Source: §II · p. 2
  • The formulation defines r_i as the probability an observation leads to a successful probe and g_i as the probability it does not stop the cascade.Source: §II · p. 2
  • The benchmark is the reward-maximizing ordered K-subset, and performance is measured by cumulative regret against its expected reward.Shortlist gaps compare each shortlist’s expected reward with the oracle policy’s reward.Source: §II · p. 2

III. ORACLE SHORTLIST POLICY · A. Optimal Oracle Shortlist: Case 2 · 1) Dynamic-Programming Subroutines:

The oracle shortlist generally requires joint selection and ordering, but per-arm selection and ordering scores can simplify the search when they exist. In Case 2, dynamic-programming subroutines handle zero-cost and positive-cost regimes, with different state spaces and computational costs.

III. ORACLE SHORTLIST POLICY

  • Per-arm selection and ordering scores can replace shortlist-wide search, though the two scores need not coincide.Theorem 1 characterizes score feasibility across four regimes defined by false-positive rates and whether costs are zero or positive.Source: §III · p. 3

A. Optimal Oracle Shortlist: Case 2

III. ORACLE SHORTLIST POLICY

  • When all arms share a channel with ϵ0 + ϵ1 < 1, µi, P(Yi = 1), and P(Xi = 1 | Yi = 1) yield identical selection and ordering rankings.Any of these quantities can serve as both scores.Source: §III · p. 3

1) Dynamic-Programming Subroutines:

  • The two oracle subroutines accept candidate vectors ρ and γ and return an optimal value and corresponding ordered shortlist.DP-ORDERED applies when τ = 0; DP-SUBSET applies when τ > 0.Source: 1) Dynamic-Programming Subroutines · p. 3
  • For τ = 0, DP-ORDERED sorts arms by ρi/(1 − γi), then uses a skip-or-include dynamic program to select K while preserving that order.Backtracking recovers the shortlist in O(L log L + LK) time.Source: 1) Dynamic-Programming Subroutines · p. 3
  • For τ > 0, DP-SUBSET jointly handles selection and positioning using states (S, m), because score-based pre-sorting no longer applies.At position m, candidate i contributes (1 − mτ)ρi and γi weights the continuation; backtracking takes O(2^L LK) time.Source: 1) Dynamic-Programming Subroutines · pp. 3–4

2) Oracle policy: dynamic programming:

The no-score oracle uses dynamic programming with the true arm parameters, making its surrogate objective equal the true reward. When position costs are zero, ordering is score-based; with positive costs, selection and positioning must be optimized jointly.

Oracle policy: dynamic programming:

  • With true parameters (r_i, g_i), the oracle’s dynamic-programming surrogate equals the true reward, and clipping is inactive because continuation values lie in [0, 1].It uses the Section III-A1 subroutines with ρ = r and γ = g.Source: 2) Oracle policy: dynamic programming · p. 4

Case 2a (τ = 0)

  • When τ = 0, the optimal ordering for any selected subset is descending in s_i^(2) = r_i/(1−g_i), as used by DP-ORDERED.The resulting oracle value at (1, K) equals R(π⋆).Source: 2) Oracle policy: dynamic programming · p. 4

Case 2b (τ > 0)

  • When τ > 0, selection and positioning are jointly coupled, so the oracle cannot pre-sort and instead uses DP-SUBSET.With ρ = r and γ = g, its value at ([L], 1) equals R(π⋆).Source: 2) Oracle policy: dynamic programming · p. 4

IV. ONLINE SCHEMES & REGRET BOUNDS · A. Score-Based UCB and Regret Bounds (Case 1 and Shared-Channel Regime)

In Case 1 and the Shared-Channel Regime, Top-K-P(Y = 1)-UCB uses each arm’s probability of a positive observation as both its selection and ordering score. Theorem 2 gives a cumulative expected regret upper bound for both regimes over horizon T.

IV. ONLINE SCHEMES & REGRET BOUNDS

  • An arm is observed when it is reached in the shortlist, and N_i(t) counts how many times arm i has been observed through round t.Source: §IV · p. 4

A. Score-Based UCB and Regret Bounds (Case 1 and Shared-Channel Regime)

  • Top-K-P(Y = 1)-UCB estimates each arm’s positive-observation probability and selects the K largest UCB indices, ranking them in descending order.The probability P(Y_i = 1) is both the selection and ordering score in these regimes.Source: A. Score-Based UCB and Regret Bounds… · p. 4
  • For arms ranked by true score, the score selection gap for a suboptimal arm a > K is Δ^s_{a,K} = s_K − s_a.Source: A. Score-Based UCB and Regret Bounds… · p. 4
  • Theorem 2 establishes a cumulative expected regret upper bound over horizon T for Algorithm 3 under Case 1 and the Shared-Channel Regime.The supplied passage does not include the bound’s formula.Source: A. Score-Based UCB and Regret Bounds… · p. 4
  • The proof splits expected regret across good-estimate and top-K-ordering events and their complements; when both events hold, regret arises only if a suboptimal arm enters the shortlist.Source: A. Score-Based UCB and Regret Bounds… · p. 4
  • When top-K UCB indices are inverted, the proof shows optimal arms are observed Ω(T) times, bounding the inversion contribution by O(1).The passage also bounds confidence-event failure by P(G^c_t) ≤ 4Lt^-3.Source: A. Score-Based UCB and Regret Bounds… · p. 4

B. From Oracle to Algorithm: DP-UCB

DP-UCB replaces unknown arm parameters with optimistic estimates and embeds them in the oracle’s dynamic program to choose and play a shortlist. Its regret is logarithmic when L > K, while the L = K setting has constant expected regret.

B. From Oracle to Algorithm: DP-UCB

  • DP-UCB uses optimistic estimates of unknown arm parameters as inputs to the oracle’s dynamic-programming subroutines, then plays the resulting shortlist and updates statistics from cascade feedback.The empirical estimators of r_i and g_i are unbiased when N_i(t) > 0.Source: B. From Oracle to Algorithm: DP-UCB · p. 5
  • When τ = 0, DP-ORDERED ranks arms by optimistic ordering score; when τ > 0, DP-SUBSET uses the general recursion without global pre-sorting.Backtracking from the corresponding dynamic-programming state yields the optimistic shortlist in each case.Source: B. From Oracle to Algorithm: DP-UCB · p. 5
  • For L > K, DP-UCB has O(LK log T) cumulative regret for both τ = 0 and τ > 0.The proof bounds the optimism contribution by a term proportional to LK log T and the failure-event contribution by O(1).Source: B. From Oracle to Algorithm: DP-UCB · p. 5
  • For L = K, DP-UCB has O(1) cumulative expected regret for both τ = 0 and τ > 0.Every arm is included and reached with probability bounded below by a positive constant, so its observation count grows linearly with time and ordering scores can be learned quickly.Source: B. From Oracle to Algorithm: DP-UCB · p. 6

V. LOWER BOUNDS

The section establishes regret lower bounds for score-based regimes and shows that the proposed scheme is order-optimal there. It also explains why obtaining an explicit analytical lower bound in the general regime is difficult.

V. LOWER BOUNDS

  • Each of the L − K suboptimal arms requires Ω(log T) expected observations under uniformly consistent policies in the score-based regimes.The proof uses a cascade-observation KL decomposition and a change-of-measure inequality to lower-bound observation counts.Source: §V · p. 6
  • For Case 1 and the Shared-Channel Regime, the lower bound matches Theorem 2’s upper bound order-wise, establishing the proposed scheme’s order-optimality.The bound applies to uniformly consistent policies.Source: §V · p. 6
  • In Case 2, deriving an explicit lower bound requires a Lai–Robbins-based optimization, but nonlinear parameter coupling prevents a tractable analytical solution for general instances.The coupling makes it difficult to express regret directly through arm observation counts.Source: §V · p. 6

VI. EXPERIMENTS

The experiments benchmark the proposed policies against Perm-UCB and Corr-UCB, and evaluate two score-based heuristics for Case 2.

VI. EXPERIMENTS

  • Perm-UCB treats all candidate shortlists as independent UCB1 actions, ignoring correlations between overlapping shortlists.The cited passage states its regret bound as O… but the supplied text omits the expression after O.Source: §VI · p. 6
  • Corr-UCB estimates cascading-feedback pseudo-rewards to exploit shortlist correlations, but Theorem 10 shows it does not improve the regret order over Perm-UCB.Corr-UCB adapts C-UCB Gupta et al. (2021); the supplied text omits the expression for the shared regret bound.Source: §VI · p. 6
  • For Case 2, the experiments also test heuristics based on P(Y = 1) and P(X = 1 | Y = 1) as score-based approximations without a valid per-arm score.The heuristics are Algorithms 3 and 8, respectively.Source: §VI · p. 6

A. Synthetic Data … VII. CONCLUSION

Synthetic, MovieLens-1M, and financial-headline experiments show DP-UCB’s sub-linear regret in no-score settings, while score-based methods also perform well when valid per-arm scores exist. The conclusion summarizes the algorithms and guarantees and notes open scalability and lower-bound questions.

A. Synthetic Data

  • In synthetic no-score instances, DP-UCB achieves sub-linear regret for K < L and K = L, while heuristics using P(Yi = 1) or P(Xi = 1 | Yi = 1) incur linear regret.The regime has no valid per-arm ranking score.Source: A. Synthetic Data · p. 6, Figure 1 · p. 7
  • In synthetic score-based instances, DP-UCB and TOP-K-P(Y = 1)-UCB achieve sub-linear regret and vastly outperform PERM-UCB and CORR-UCB; TOP-K-P(Y = 1)-UCB outperforms DP-UCB by exploiting the score structure.This regime has vanishing false-positive rates (ϵ0 = 0L) and ranking scores via P(Yi = 1).Source: A. Synthetic Data · p. 6, Figure 1 · p. 7
  • In the synthetic shared-channel regime, TOP-P(X = 1 | Y = 1)-UCB, TOP-P(Y = 1)-UCB, and DP-UCB achieve sub-linear regret and significantly outperform other baselines.Both P(Yi = 1) and P(Xi = 1 | Yi = 1) serve as ranking scores when noise models are common across arms.Source: A. Synthetic Data · p. 6, Figure 1 · p. 7

B. MovieLens Real-World Benchmark

  • On MovieLens-1M, DP-UCB maintains sub-linear regret in no-score settings where ranking-score heuristics incur linear regret, and score-based methods also achieve sub-linear regret.The no-score comparison covers τ = 0.15 and τ = 0; in the score-based regime, DP-UCB and TOP-K-P(Y = 1)-UCB substantially outperform other baselines.Source: Figure 2 · p. 7, B. MovieLens Real-World Benchmark · p. 7

VII. CONCLUSION

  • The conclusion presents TOP-K-P(Y = 1)-UCB with an order-optimal regret guarantee for the score-based regime and DP-UCB’s dynamic programming approach and analytical guarantees for the no-score regime.It also notes that dynamic programming may be prohibitive for large action spaces under positive observation cost, and tractable regret lower bounds for the general no-score regime remain open.Source: §VII · p. 8

C. LLM Headlines Cascade

  • On financial headlines, DP-UCB achieves sub-linear regret for K < L and K = L, while score-based heuristics incur linear regret in both configurations.The experiment routes headlines through five generator-and-judge arms and evaluates K = 3, L = 5, τ = 0.20 and K = L = 5, τ = 0.18.Source: Figure 3 · p. 8, C. LLM Headlines Cascade · p. 8

APPENDIX CASCADING BANDITS WITH NOISY OBSERVATIONS: … A. Proof of Correctness for DP-ORDERED (τ = 0)

The appendix analyzes when arm scores suffice for ordering or selection and gives counterexamples showing how false positives and positive inspection costs can make decisions depend on the cascade. It also establishes the correctness scope of the dynamic-programming oracles, including a backward-induction proof that DP-ORDERED at zero inspection cost maximizes expected reward over valid shortlists while respecting probability bounds.

Part I: ordering score:

  • With no false positives, arms can be ordered by s(2) when τ > 0, while at τ = 0 swapping arms leaves reward unchanged; with false positives and τ = 0, the ordering score is ri/(1 − gi).When false positives occur with τ > 0, the swap comparison can reverse with position, so no arm-only ordering score exists under the stated conditions.Source: Part I: ordering score · p. 12

Part II: selection score:

  • With no false positives, the optimal shortlist consists of the K arms with the largest r-values; if false positives occur, no context-independent selection score exists.The selection preference can reverse as the suffix changes, even when the compared arms’ own parameters remain fixed.Source: Part II: selection score · pp. 12–13

Part III: µi under a Shared Channel:

  • Under a shared informative channel with identical false-positive and false-negative rates across arms and τ = 0, sorting by true means µi maximizes reward and also determines the optimal shortlist and order.The proof identifies 1 − gi and ri/(1 − gi) as equivalent scores because both rank arms identically to µi.Source: Part III: µi under a Shared Channel · p. 13

IX. CASE 2: NUMERICAL NON-SEPARABILITY OF ARM SELECTION

  • Across six numerical examples, fixed reference arms reverse their selection into the optimal shortlist when other arms are perturbed, demonstrating that no context-independent selection score exists in Cases 2a and 2b.Examples 1–4 use τ > 0; Examples 5–6 use τ = 0.Source: §IX · p. 15

A. Case 2: Numerical Non-Separability of Arm Ordering

  • In Case 2b, perturbing an auxiliary arm reverses the optimal relative order of fixed candidate arms, including when K = L, confirming that no scalar ordering score exists.The examples hold the compared arms’ parameters fixed while changing another arm in the cascade.Source: A. Case 2: Numerical Non-Separability… · pp. 15–16

X. PROOFS FOR DYNAMIC PROGRAMMING ORACLES

  • The dynamic-programming oracle section states that DP-ORDERED and DP-SUBSET compute the optimal expected reward for τ = 0 and τ > 0, respectively.For DP-ORDERED, the proof restricts the search to ordered subsequences after pre-sorting arms by ri/(1 − gi).Source: §X · p. 16, A. Proof of Correctness for DP-ORDERED… · p. 16

A. Proof of Correctness for DP-ORDERED (τ = 0)

B. Correctness of DP-SUBSET (τ > 0) … State Space Definition

The merged sections describe algorithms and proof tools for cascading bandits, including subset-based optimization under positive position costs, regret decompositions, and a Markov-chain state space.

B. Correctness of DP-SUBSET (τ > 0)

  • Backward induction shows DP-SUBSET’s value equals the maximum attainable suffix reward and is at most 1, establishing optimality for τ > 0.Position costs couple arm selection and sequencing, so the algorithm optimizes jointly over candidate subsets.Source: B. Correctness of DP-SUBSET (τ > 0) · pp. 17–18

XI. PSEUDO-CODES OF ALGORITHMS

  • The case-1 UCB procedure initializes arm counts and estimates, selects the K largest UCB indices, then updates observed arms after feedback.It plays the selected shortlist until the first Y = 1 or all K arms have been observed.Source: §XI · p. 19

A. DP-based Algorithms

  • For τ = 0, DP-Ordered uses score ordering; for τ > 0, DP-SUBSET optimizes without selection or ordering scores.The suffix recursion scales future reward by the probability of continuing past the current position.Source: A. DP-based Algorithms · p. 19

XII. AUXILIARY LEMMAS

  • The auxiliary-lemmas section introduces supporting results used in the paper’s lower-bound proofs.Source: §XII · p. 20

A. Concentration Event and Failure Probability

  • The concentration lemma bounds the probability of the complementary good event at each step and its sum over T steps.The proof invokes a union bound and Hoeffding’s inequality.Source: A. Concentration Event and Failure… · p. 20

B. Reward Decomposition Identities

  • The reward-decomposition lemmas express case-1 and general case-2 regret as telescoping sums across hybrid shortlists, with position-wise gaps in case 2.The case-1 decomposition also uses a position-dependent weight factor.Source: B. Reward Decomposition Identities · pp. 21–22

XIII. DIVERGENCE DECOMPOSITION

  • The divergence-decomposition section defines u_i as P(Y_i = 1) and v_i as P(X_i = 1 | Y_i = 1).Source: §XIII · p. 22

State Space Definition

  • The Markov-chain state space distinguishes no observed positive feedback, a first relevant arm with X = 1, and one with X = 0.The latter two states both specify Y = 1 at the first relevant position.Source: State Space Definition · p. 23

Transition Probabilities … C. Bounding the Regret Component R12

This section bounds regret by decomposing trajectory divergences and regret into components, including selection regret and ordering-disruption regret among optimal arms, which is shown to be O(1) independent of the horizon.

Transition Probabilities

  • Trajectory KL divergence decomposes into per-arm contributions weighted by how often each arm is observed.The trajectory decomposition uses the observation indicator O_t,a and sums over rounds; the policy terms cancel because the policy conditioned on history is parameter-independent.Source: Transition Probabilities · pp. 23–24

A. Regret Decomposition

  • Regret is separated into R11 for suboptimal selection with optimal ordering preserved, R12 for optimal-arm ordering disruptions, and R2 for concentration failures.The decomposition assumes single-round regret is bounded between zero and one.Source: A. Regret Decomposition · p. 25

B. Bounding R11

  • Under preserved ordering of optimal arms, R11 is bounded by summing regret from suboptimal placements and controlling their observed counts with UCB concentration.Optimal placements have non-positive gaps under the ordering event, so they do not contribute positive selection regret.Source: B. Bounding R11 · pp. 26–27

C. Bounding the Regret Component R12

  • O(1) cumulative regret bounds R12, the component caused by ordering disruptions among optimal arms under concentration success.The proof establishes this bound through auxiliary results on observation concentration, suboptimal-selection thresholds, optimal-subset plays, and inversion probabilities.Source: C. Bounding the Regret Component R12 · p. 27
  • Observation concentration and a UCB contradiction lemma control suboptimal selections, yielding a summable probability bound for exceeding their selection thresholds.The proof bounds the per-time threshold-exceedance probability by t^-3 before summing over the horizon.Source: C. Bounding the Regret Component R12 · pp. 27–28
  • Under h_t, optimal-subset plays lower-bound every optimal arm’s inclusions, while an ordering inversion requires an adjacent pair of optimal arms to be misordered.The subset-play count satisfies T′(t) ≥ t − c(L−K) log t; the inversion argument reduces the event to confidence-bound comparisons and observation counts.Source: C. Bounding the Regret Component R12 · pp. 28–29
  • R12 = O(1): partitioning on the good event bounds the bad-event contribution and makes the remaining regret summable over time and adjacent optimal pairs.The resulting finite constant depends on problem parameters, including observation probabilities and gaps, but not on T.Source: C. Bounding the Regret Component R12 · pp. 30–31
  • Across rounds selecting the optimal set, N_b+1(t) stochastically dominates T′(t) Bernoulli trials with observation probability p_b+1.Arm b+1 is selected in every such round, and its worst-case-position observation probability is at least p_b+1.Source: C. Bounding the Regret Component R12 · p. 30
  • After splitting the sum at threshold time τ_b, the tail terms converge to a finite constant independent of T.The constant depends on p_b+1, the gap Δ_s b,b+1, L, and K.Source: C. Bounding the Regret Component R12 · p. 31

D. Proof of Theorem 2 · XV. DYNAMIC PROGRAMMING REGRET BOUNDS

The proof of Theorem 2 combines regret and selection bounds, while the dynamic-programming regret analysis establishes recursive optimism and bounds the shortlist’s suffix-value gap. The analysis covers both DP-SUBSET and DP-ORDERED.

D. Proof of Theorem 2

  • Theorem 2 follows by combining the regret decomposition, regret bound, and suboptimal-arm selection bound, then grouping O(1) terms.The proof identifies Lemmas 9, 18, and 11 as the ingredients.Source: D. Proof of Theorem 2 · p. 31

XV. DYNAMIC PROGRAMMING REGRET BOUNDS

  • For τ > 0, DP-SUBSET’s positional recurrence follows from its state over the remaining slot budget and active candidate set.The proof identifies the state and relates it to the shortlist’s positional values and boundary condition.Source: §XV · p. 31
  • For τ = 0, DP-ORDERED’s positional recurrence follows by selecting shortlist positions from a global ordering of all L candidates.The proof uses the ordered dynamic program and telescopes across skipped candidates between selected positions.Source: §XV · p. 32
  • With probability at least 1 − 4Kt^-2, the recursive value estimate upper-bounds the true suffix value at every position.The proof establishes optimism by backward induction, using the positional recurrence and the fact that suffix values lie in [0, 1].Source: §XV · p. 32
  • Under the good event, Lemma 21 bounds the full-shortlist optimism gap by separating single-arm estimation errors from downstream suffix terms.The suffix-gap argument proceeds by backward induction and specializes the resulting bound to position m = 1.Source: §XV · pp. 32–33
  • The good-event gap bound uses arm confidence bounds and the condition (1 − kτ) ≤ 1 − τ for τ ≥ 0 and k ≥ 1.These bounds are substituted into the position-1 gap expression to complete the argument.Source: §XV · p. 33

A. Proof of Theorem 3 · XVI. PROOF OF THEOREM 4 · B. Proof of Theorem 4 when τ = 0

The proofs control regret through good-event confidence bounds and observation counts. Theorem 4 treats positive and zero noise separately, with both cases yielding horizon-independent expected regret.

A. Proof of Theorem 3

  • For Theorem 3, optimism and dynamic-programming optimality bound good-event regret using the selected shortlist’s arm observation counts.The proof uses the minimum nonzero regret gap when the selected shortlist differs from the optimal shortlist.Source: A. Proof of Theorem 3 · pp. 33–34
  • Theorem 3’s proof sums regret over observed arm counts, then adds a concentration-failure bound from Lemma 3.It defines a per-arm observation threshold beyond which the bracketed regret contribution vanishes.Source: A. Proof of Theorem 3 · p. 34

XVI. PROOF OF THEOREM 4

  • Theorem 4’s proof splits into separate cases for τ > 0 and τ = 0.Source: §XVI · p. 34
  • When τ > 0, a suboptimal ordering on the good event requires at least one selected arm’s observation count to be at or below the threshold.The proof derives this by contradiction from UCB selection, optimism, and the minimum suboptimality gap.Source: §XVI · pp. 34–35
  • For τ > 0, the proof establishes E[R(T)] = O(1), independent of horizon T.The result follows after summing the regret bound and accounting for concentration failure.Source: §XVI · p. 35

B. Proof of Theorem 4 when τ = 0

  • When τ = 0, the proof bounds ordering error by considering adjacent misordered arms and then bounding their low observation-count probabilities.The thresholds are defined using normalized adjacent gaps, and the tail bounds use Lemma 17.Source: B. Proof of Theorem 4 when τ = 0 · p. 36

XVII. LOWER BOUNDS FOR CASE 1 · XVIII. LOWER BOUNDS IN SHARED CHANNEL REGIME

The sections establish asymptotic instance-dependent regret lower bounds for Case 1 and the shared-channel regime. Their lemmas relate regret to observations of suboptimal arms and the placement of arms in the ordered shortlist.

XVII. LOWER BOUNDS FOR CASE 1

  • For a fixed set of arms, placing larger success probabilities earlier maximizes expected payoff and supports a regret decomposition by ordering.Lemma 22 states the single-step regret decomposition; the accompanying explanation establishes ordering optimality.Source: §XVII · p. 37
  • Lemma 23 lower-bounds cumulative regret through observation counts of suboptimal arms and a position-substitution constant.The observation count is defined from whether an arm is selected and observed under the played shortlist.Source: §XVII · p. 38
  • Under Case 1, Theorem 8 gives an instance-dependent regret lower bound for every uniformly consistent policy.The section restates Theorem 5 with complete technical details in Theorem 8.Source: §XVII · pp. 37, 39

XVIII. LOWER BOUNDS IN SHARED CHANNEL REGIME

  • Lemma 24 gives a cumulative regret lower bound in the shared-channel regime in terms of arm observation counts.Its constants are defined as in Theorem 9.Source: §XVIII · p. 40
  • In the shared-channel derivation, the uniform gap bound supports the cumulative lower bound after accounting for the positions occupied by suboptimal arms.The derivation uses the ordering by μi and discards positions occupied by optimal arms.Source: §XVIII · p. 41
  • Under a shared channel with ε0 + ε1 < 1, Theorem 9 gives a regret lower bound for every uniformly consistent policy.In this regime, ui, vi, and μi provide equivalent arm rankings.Source: §XVIII · pp. 40–41

XIX. LOWER BOUND FOR THE GENERAL REGIME … C. LLM experiments supplement

The paper derives a general-regime regret lower bound and examines where shortlist-based baselines fail to exploit cascade structure. Supplementary experiments show DP-UCB’s sub-linear regret in larger MovieLens cascades and describe an LLM-routing evaluation setup.

XIX. LOWER BOUND FOR THE GENERAL REGIME

  • Any uniformly consistent policy must satisfy a Lai and Robbins (1985) lower-bound framework, but solving its optimization over all valid permutations is challenging in the general regime.The bound’s optimization value is defined through alternative parameter configurations, while nonlinear coupling between ui and vi impedes an explicit analytical solution.Source: §XIX · pp. 42–43

A. Naive Shortlist Bandit (Perm-UCB)

B. Cascaded Correlated UCB (Corr-UCB)

  • Corr-UCB uses optimistic conditional bounds over compatible latent states to exploit overlap among shortlists, adapting the C-UCB framework of Gupta et al. (2021).Its optimistic bound maximizes a target shortlist’s reward over latent states consistent with the observed cascade feedback.Source: B. Cascaded Correlated UCB (Corr-UCB) · p. 43

C. Structural Bottleneck and Regret Analysis

  • In cascade models, every shortlist is competitive under correlated feedback, so C-UCB obtains no structural pruning and its regret bound scales with the full shortlist space.Theorem 10 establishes ψπ,π∗ ≥ wπ∗ for any shortlist π; consequently C = |PL,K| = L!/(L−K)!.Source: C. Structural Bottleneck and Regret… · p. 44

D. Score-based Evaluation

  • The score-based evaluation forms a shortlist by sorting arms on the ratio of optimistic reward to one minus optimistic termination probability.It updates reward and termination estimates for observed arms and carries estimates forward for unobserved arms.Source: D. Score-based Evaluation · p. 44

Discussion of Supplementary Results

Dataset details

  • The MovieLens-1M evaluation models genres as arms, uses the top L = 10 rated genres, and binarizes ratings at 4 or higher; the supplement also reports synthetic experiment parameter configurations.MovieLens-1M contains 1,000,000 ratings across 3,883 movies from 6,040 users; false-positive and false-negative rates are introduced synthetically for genre arms.Source: Experimental Parameters synthetic · pp. 44–45, Dataset details · p. 45, Table III · p. 45

Additional experiments and Parameters

Related papers

Loading 2610.29381v1…