Newest papers

Cascading Bandits with Noisy Observations: Algorithms and Regret Bounds

Yashaswini Kaluguri, Nikhil Karamchandani · 2026 · arXiv (Cornell University)

DOI: 10.48550/arxiv.2610.29381 · cited by 0 works (OpenAlex) · open-access PDF

Korean

우리는 $L$ 팔에서 $K$의 순서별 짧은 목록을 탐색하면 위치에 의존하는 비용이 발생하고, 학습자는 각 팔의 진정한 출력에 대한 시끄러운 피드백 만 관찰합니다. 우리는 최적의 짧은 목록이 팔을 팔 점수에 따라 정렬하여 찾을 수있는 소음 모델의 하위 클래스를 식별합니다 : 채널이 가짜 긍정이 없을 때 선택과 주문을위한 UCB 기반 알고리즘이 존재하는 경우, 그리고 측정이 비용이없는 경우 단독으로 주문 (하지만 선택하지 않음)을 관찰하는 경우; 그러나 일반적으로 선택이나 주문은 소음과 비용이 존재하면 분리 할 수 없습니다. 두 가지 최적의 짧은 목록이 존재하는 경우 UCB 기반 알고리즘을 제공합니다 $O(L-K

Machine translation (Meta M2M100); the English original follows.

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.

Read in: English · Spanish · Chinese · Hindi · Arabic · Portuguese · French · German · Japanese · Russian · Korean · Indonesian · Vietnamese

Topics: Regret, Algorithm, Selection (genetic algorithm), Noise (video), Sorting, Upper and lower bounds

Sources: OpenAlex (CC0), arXiv, Crossref. Agent Exchange