Efficient algorithms for noisy cascading bandits with position costs
Cascading Bandits with Noisy Observations: Algorithms and Regret Bounds
Machine Learning
Summary
This paper studies a problem where you try to find the best list of items to check, but checking each item has a cost that depends on its position. The observations about each item are noisy, so it's hard to know the true value. The authors identify conditions where sorting items by a simple score works well and propose algorithms that learn the best list over time. They also provide theoretical guarantees on the learning performance and show results on simulated and real data.
What this means in practice
- •For online recommendation teams: Optimize ranked lists of recommended items under noisy user feedback and position-dependent costs.
- •For industrial inspection planners: Schedule costly inspections of ordered components when observations can be noisy to minimize inspection time and errors.
Authors
Yashaswini Kaluguri, Nikhil Karamchandani
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.