Cascading Bandits with Noisy Observations: Algorithms and Regret Bounds

Yashaswini Kaluguri; Nikhil Karamchandani

cs.LGOct 21, 2026

Cascading Bandits with Noisy Observations: Algorithms and Regret Bounds

Authors: Yashaswini Kaluguri, Nikhil Karamchandani

Organizations: Department of Electrical Engineering, Indian Institute of Technology Bombay, Mumbai, India

Abstract

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.

Figures & tables

	Cost-free ( $\tau=0$ )		Costly ( $\tau>0$ )
Regime	$s_{i}^{(1)}$	$s_{i}^{(2)}$	$s_{i}^{(1)}=s_{i}^{(2)}$
Case 1 ( $\epsilon_{0,i}=0\hskip 8.50012pt\forall i\in[L]$ )	(Case 1a)		(Case 1b)
	$1-g_{i}=(1-\epsilon_{1,i})\mu_{i}$	order doesn’t matter	$1-g_{i}=(1-\epsilon_{1,i})\mu_{i}$
Case 2 ( $\epsilon_{0,i}>0$ for some $i$ )	(Case 2a)		(Case 2b)
	No score	$\frac{r_{i}}{1-g_{i}}=\frac{(1-\epsilon_{1,i})\mu_{i}}{(1-\epsilon_{1,i})\mu_{i}+\epsilon_{0,i}(1-\mu_{i})}$	No score

TABLE I : Selection score

s_{i}^{(1)}

and ordering score

s_{i}^{(2)}

across the four named regimes (Theorem 1 ).

Panel of Figure 2 — Fig. 1 : Cumulative regret vs. time. (a)–(c) Case 1 (Score): $\boldsymbol{\epsilon}_{0}=\mathbf{0}_{6}$ , Top- $K$ - $P(Y=1)$ -UCB vs. DP-UCB . (d)–(e) Case 2 (no-score): Regret for $K<L$ and $K=L$ . (f) Shared-Channel: $K=3,L=6,\tau=0.15$ .

Panel of Figure 3 — Fig. 2 : Cumulative regret vs. time on MovieLens-1M. (a) Case 1 (Score regime): $\boldsymbol{\epsilon}_{0}=\mathbf{0}_{10}$ . (b) Case 2 (No-score regime): $\tau=0.15$ . (c) Case 2 (No-score regime): $\tau=0$ .

Arm	Generator (LLM)	Discriminator (Judge)	$\mu$	$\epsilon_{1}$	$\epsilon_{0}$
$1$	SmolLM2-1.7B-Instruct	bert-base-uncased	$0.7036$	$0.0387$	$0.1596$
$2$	Qwen2.5-0.5B-Instruct	roberta-base	$0.6496$	$0.0328$	$0.2182$
$3$	phi-2	electra-base-discriminator	$0.7462$	$0.0444$	$0.3463$
$4$	stablelm-2-1_6b-chat	albert-base-v2	$0.6579$	$0.0761$	$0.2074$
$5$	SmolLM2-360M-Instruct	DeBERTa-v3-base	$0.4155$	$0.1328$	$0.0398$

TABLE II : Empirical parameters for LLM-judge cascade arms across the financial headlines dataset.

Panel of Figure 5 — Fig. 3 : Cumulative regret on LLM Headlines.

Panel of Figure 6 — Fig. 4 : cumulative regret on MovieLens-1M . (a) Zero-cost regime ( $\tau=0,K=3$ ). (b) DP-UCB regret scaling ( $K=3$ vs. $K=6$ ). (c) Shared-channel zero-cost setting ( $\tau=0,\boldsymbol{\epsilon}_{1}=0.3\mathbf{1}_{6},\boldsymbol{\epsilon}_{0}=0.2\mathbf{1}_{6}$ ).

Regime	Vector	Parameter Values	Figure Reference
Case 1	$\boldsymbol{\mu}$	$[0.5595,0.9104,0.2653,0.9089,0.3995,0.4887]^{\top}$	Fig. 1 (a)–(c)
(Score)	$\boldsymbol{\epsilon}_{1}$	$[0.3987,0.4253,0.3167,0.1038,0.1080,0.4177]^{\top}$
	$\boldsymbol{\epsilon}_{0}$	$[0.0000,0.0000,0.0000,0.0000,0.0000,0.0000]^{\top}$
Case 2	$\boldsymbol{\mu}$	$[0.5595,0.9104,0.2653,0.9089,0.3995,0.4887]^{\top}$	Fig. 1 (d)–(e),
(General)	$\boldsymbol{\epsilon}_{1}$	$[0.3987,0.4253,0.3167,0.1038,0.1080,0.4177]^{\top}$	Fig. 4 (a)–(b)
	$\boldsymbol{\epsilon}_{0}$	$[0.1266,0.1573,0.4879,0.2698,0.4306,0.3222]^{\top}$

TABLE III : Parameter configurations across all empirical evaluation regimes (

L=6

Fig. 5 : Empirical cumulative regret on MovieLens-1M under a larger cascade slate (

L=10,K=5,\tau=0.15,T=500{,}000

, 100 trials). Heuristic rankings based on

P(Y_{i}=1)

P(X_{i}=1\mid Y_{i}=1)

suffer linear regret, whereas DP-UCB scales efficiently and maintains sub-linear regret.

Genre (Arm $i$ )	Mean ( $\mu_{i}$ )	False Negative ( $\epsilon_{1,i}$ )	False Positive ( $\epsilon_{0,i}$ )
Film-Noir	$0.7250$	$0.1289$	$0.1780$
Mystery	$0.6560$	$0.3979$	$0.4692$
Crime	$0.6250$	$0.4771$	$0.0202$
Documentary	$0.5930$	$0.4290$	$0.0170$
Drama	$0.5550$	$0.1072$	$0.0684$
Musical	$0.5330$	$0.1154$	$0.4110$

TABLE IV : MovieLens-1M parameter configurations (

L=10

). Note that

\boldsymbol{\epsilon}_{0}=\mathbf{0}_{10}

rest of the parameters being same is used for Figure 2 (a) (score-based regime).

Multi-Armed Bandits

Multi-Armed Bandits study how to choose among uncertain actions over time while balancing immediate rewards with learning.

See all 348 papers

Cost-Ordered Feasibility for Multi-Armed Bandits with Cost Subsidy
May 8, 2026Ishank Juneja, Carlee Joe-Wong, Osman YağanMulti-Armed Bandits Robust Multi-Armed Bandits
Department of Electrical and Computer Engineering Carnegie Mellon University Pittsburgh, PA 15213
Learning in Markovian bandits with non-observable states and constrained decision epochs
Jun 25, 2026Thomas Hira, Victor Boone, Urtzi Ayesta +1Multi-Armed Bandits Markov Models
IRIT, Université de Toulouse, CNRS, Toulouse INP, Toulouse, France · Ikerbasque-UPV/EHU, University of the Basque Country, Bilbao, Spain
Prior-Free Competitive Ratios for Improving Bandits: Scale, Curvature and Horizon Are Free, but Not Jointly Under Noise
Sep 12, 2026Xuan LiMulti-Armed Bandits Competitive Analysis
University of New South Wales, Sydney, Australia

May 8, 2026J/K move · Enter open · S save

Cost-Ordered Feasibility for Multi-Armed Bandits with Cost Subsidy

Ishank Juneja, Carlee Joe-Wong, Osman Yağan

Department of Electrical and Computer Engineering Carnegie Mellon University Pittsburgh, PA 15213

Multi-Armed Bandits Robust Multi-Armed Bandits

Open paper AskPDF arXiv

The classic multi-armed bandit (MAB) problem tackles the challenge of accruing maximum reward while making decisions under uncertainty. However, in applications, often the goal is to minimize cost subject to a constraint on the minimum permissible reward, an objective captured by multi-armed bandits with cost-subsidy (MAB-CS). Of interest to this paper is the setting where the quality (reward) constraint is specified relative to the unknown best reward and the cost of each arm is known. We characterize the expected sub-optimal samples required by any policy by proving instance-dependent lower bounds that offer new insight into the problem and are a strict generalization of prior bounds. Then, we propose an algorithm called Cost-Ordered Feasibility (COF) that leverages our insight and intelligently combine samples from all arms to gauge the feasibility of a cheap arm. Thereafter, we analyze COF to establish instance-dependent upper bounds on its expected cumulative cost and quality regret, i.e., relative to the cheapest feasible arm. Finally, we empirically validate the merits of COF, comparing it to baselines from the literature through extensive simulation experiments on the MovieLens and Goodreads datasets as well as representative synthetic instances. Not only does our paper develop qualitatively better theoretical regret upper bounds, but COF also convincingly demonstrates improved empirical performance.

Abstract

Multi-Armed Bandits

Explore similar work

Cost-Ordered Feasibility for Multi-Armed Bandits with Cost Subsidy

Learning in Markovian bandits with non-observable states and constrained decision epochs

Prior-Free Competitive Ratios for Improving Bandits: Scale, Curvature and Horizon Are Free, but Not Jointly Under Noise