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

Arabic

ونحن نقدم إعدادًا جديدًا للصواريخ البلاستيكية، حيث يتم تحديد القائمة المرتقبة من $K$ من أسلحة $L$، حيث تتعرض القائمة إلى تكلفة متصلة بالواقع، وتتبع المتعلم فقط ردود الفعل المزعجة حول النتائج الحقيقية لكل ذراع. ونحن نحدد فئة من النماذج الصوتية التي يمكن تحديد القائمة المثالية عن طريق تقسيم الذراع وفقًا لمستوى ذراع: فإن هذه النماذج موجودة على سبيل المثال لكل من الاختيار والتنظيم عندما لا يوجد قناة إيجابية خاطئة، وإذا كان الاختيار فقط (ولكن ليس الاختيار) عندما تكون التقييمات غير مكلفة؛ ومع ذلك، بشكل عام، لا يمكن تمييز الاختيار أو التقييم مرة واحدة بعد

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