Cascading Bandits with Noisy Observations: Algorithms and Regret Bounds
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(LKlog T) regret. Finally, we validate our theoretical results through extensive numerical evaluations and simulations over both synthetic and real-world datasets.
Related
- Near-Optimal Regret Bounds for UCB-Style Gaussian Process Bandits via Data Thinning
- Toward Optimal Switching Regret for Multi-Armed Bandits with Oblivious Adversary
- Exact Regret Frontiers and Externality Scheduling in Centralized Serial-Dictatorship Bandits
- Bandits with Multiple Optimal Arms: Minimax Regret and Non-Adaptivity
- Exact Bayes Regret and Asymptotic Optimality in High-Dimensional Gaussian Bandits
BibTeX
@misc{kaluguri2026cascading,
title = {{Cascading Bandits with Noisy Observations: Algorithms and Regret Bounds}},
author = {Yashaswini Kaluguri and Nikhil Karamchandani},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.29381},
eprint = {2610.29381},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.29381},
}
RIS
TY - UNPB
TI - Cascading Bandits with Noisy Observations: Algorithms and Regret Bounds
AU - Yashaswini Kaluguri
AU - Nikhil Karamchandani
PY - 2026
DA - 2026/10/21
PB - arXiv
DO - 10.48550/arxiv.2610.29381
UR - https://arxiv.org/abs/2610.29381
AB - 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(LKlog T) regret. Finally, we validate our theoretical results through extensive numerical evaluations and simulations over both synthetic and real-world datasets.
ER -